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` 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.
38 // We put in the elements into the queue only in the toplevel decl check
41 // static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
42 // Decl *D1, Decl *D2);
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.
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**
59 //===----------------------------------------------------------------------===//
61 #include "clang/AST/ASTStructuralEquivalence.h"
62 #include "clang/AST/ASTContext.h"
63 #include "clang/AST/ASTDiagnostic.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"
71 #include "clang/AST/NestedNameSpecifier.h"
72 #include "clang/AST/TemplateBase.h"
73 #include "clang/AST/TemplateName.h"
74 #include "clang/AST/Type.h"
75 #include "clang/Basic/ExceptionSpecificationType.h"
76 #include "clang/Basic/IdentifierTable.h"
77 #include "clang/Basic/LLVM.h"
78 #include "clang/Basic/SourceLocation.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"
89 using namespace clang;
91 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
92 QualType T1, QualType T2);
93 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
95 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
96 const TemplateArgument &Arg1,
97 const TemplateArgument &Arg2);
98 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
99 NestedNameSpecifier *NNS1,
100 NestedNameSpecifier *NNS2);
101 static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
102 const IdentifierInfo *Name2);
104 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
105 const DeclarationName Name1,
106 const DeclarationName Name2) {
107 if (Name1.getNameKind() != Name2.getNameKind())
110 switch (Name1.getNameKind()) {
112 case DeclarationName::Identifier:
113 return IsStructurallyEquivalent(Name1.getAsIdentifierInfo(),
114 Name2.getAsIdentifierInfo());
116 case DeclarationName::CXXConstructorName:
117 case DeclarationName::CXXDestructorName:
118 case DeclarationName::CXXConversionFunctionName:
119 return IsStructurallyEquivalent(Context, Name1.getCXXNameType(),
120 Name2.getCXXNameType());
122 case DeclarationName::CXXDeductionGuideName: {
123 if (!IsStructurallyEquivalent(
124 Context, Name1.getCXXDeductionGuideTemplate()->getDeclName(),
125 Name2.getCXXDeductionGuideTemplate()->getDeclName()))
127 return IsStructurallyEquivalent(Context,
128 Name1.getCXXDeductionGuideTemplate(),
129 Name2.getCXXDeductionGuideTemplate());
132 case DeclarationName::CXXOperatorName:
133 return Name1.getCXXOverloadedOperator() == Name2.getCXXOverloadedOperator();
135 case DeclarationName::CXXLiteralOperatorName:
136 return IsStructurallyEquivalent(Name1.getCXXLiteralIdentifier(),
137 Name2.getCXXLiteralIdentifier());
139 case DeclarationName::CXXUsingDirective:
140 return true; // FIXME When do we consider two using directives equal?
142 case DeclarationName::ObjCZeroArgSelector:
143 case DeclarationName::ObjCOneArgSelector:
144 case DeclarationName::ObjCMultiArgSelector:
145 return true; // FIXME
148 llvm_unreachable("Unhandled kind of DeclarationName");
152 /// Determine structural equivalence of two expressions.
153 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
154 const Expr *E1, const Expr *E2) {
158 if (auto *DE1 = dyn_cast<DependentScopeDeclRefExpr>(E1)) {
159 auto *DE2 = dyn_cast<DependentScopeDeclRefExpr>(E2);
162 if (!IsStructurallyEquivalent(Context, DE1->getDeclName(),
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);
171 if (!IsStructurallyEquivalent(Context, CastE1->getType(),
174 return IsStructurallyEquivalent(Context, CastE1->getSubExpr(),
175 CastE2->getSubExpr());
177 // FIXME: Handle other kind of expressions!
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;
187 return Name1->getName() == Name2->getName();
190 /// Determine whether two nested-name-specifiers are equivalent.
191 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
192 NestedNameSpecifier *NNS1,
193 NestedNameSpecifier *NNS2) {
194 if (NNS1->getKind() != NNS2->getKind())
197 NestedNameSpecifier *Prefix1 = NNS1->getPrefix(),
198 *Prefix2 = NNS2->getPrefix();
199 if ((bool)Prefix1 != (bool)Prefix2)
203 if (!IsStructurallyEquivalent(Context, Prefix1, Prefix2))
206 switch (NNS1->getKind()) {
207 case NestedNameSpecifier::Identifier:
208 return IsStructurallyEquivalent(NNS1->getAsIdentifier(),
209 NNS2->getAsIdentifier());
210 case NestedNameSpecifier::Namespace:
211 return IsStructurallyEquivalent(Context, NNS1->getAsNamespace(),
212 NNS2->getAsNamespace());
213 case NestedNameSpecifier::NamespaceAlias:
214 return IsStructurallyEquivalent(Context, NNS1->getAsNamespaceAlias(),
215 NNS2->getAsNamespaceAlias());
216 case NestedNameSpecifier::TypeSpec:
217 case NestedNameSpecifier::TypeSpecWithTemplate:
218 return IsStructurallyEquivalent(Context, QualType(NNS1->getAsType(), 0),
219 QualType(NNS2->getAsType(), 0));
220 case NestedNameSpecifier::Global:
222 case NestedNameSpecifier::Super:
223 return IsStructurallyEquivalent(Context, NNS1->getAsRecordDecl(),
224 NNS2->getAsRecordDecl());
229 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
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))
237 // If the kind is different we compare only the template decl.
238 if (N1.getKind() != N2.getKind())
240 } else if (TemplateDeclN1 || TemplateDeclN2)
242 else if (N1.getKind() != N2.getKind())
245 // Check for special case incompatibilities.
246 switch (N1.getKind()) {
248 case TemplateName::OverloadedTemplate: {
249 OverloadedTemplateStorage *OS1 = N1.getAsOverloadedTemplate(),
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))
256 return I1 == E1 && I2 == E2;
259 case TemplateName::AssumedTemplate: {
260 AssumedTemplateStorage *TN1 = N1.getAsAssumedTemplateName(),
261 *TN2 = N1.getAsAssumedTemplateName();
262 return TN1->getDeclName() == TN2->getDeclName();
265 case TemplateName::DependentTemplate: {
266 DependentTemplateName *DN1 = N1.getAsDependentTemplateName(),
267 *DN2 = N2.getAsDependentTemplateName();
268 if (!IsStructurallyEquivalent(Context, DN1->getQualifier(),
269 DN2->getQualifier()))
271 if (DN1->isIdentifier() && DN2->isIdentifier())
272 return IsStructurallyEquivalent(DN1->getIdentifier(),
273 DN2->getIdentifier());
274 else if (DN1->isOverloadedOperator() && DN2->isOverloadedOperator())
275 return DN1->getOperator() == DN2->getOperator();
279 case TemplateName::SubstTemplateTemplateParmPack: {
280 SubstTemplateTemplateParmPackStorage
281 *P1 = N1.getAsSubstTemplateTemplateParmPack(),
282 *P2 = N2.getAsSubstTemplateTemplateParmPack();
283 return IsStructurallyEquivalent(Context, P1->getArgumentPack(),
284 P2->getArgumentPack()) &&
285 IsStructurallyEquivalent(Context, P1->getParameterPack(),
286 P2->getParameterPack());
289 case TemplateName::Template:
290 case TemplateName::QualifiedTemplate:
291 case TemplateName::SubstTemplateTemplateParm:
292 // It is sufficient to check value of getAsTemplateDecl.
300 /// Determine whether two template arguments are equivalent.
301 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
302 const TemplateArgument &Arg1,
303 const TemplateArgument &Arg2) {
304 if (Arg1.getKind() != Arg2.getKind())
307 switch (Arg1.getKind()) {
308 case TemplateArgument::Null:
311 case TemplateArgument::Type:
312 return IsStructurallyEquivalent(Context, Arg1.getAsType(), Arg2.getAsType());
314 case TemplateArgument::Integral:
315 if (!IsStructurallyEquivalent(Context, Arg1.getIntegralType(),
316 Arg2.getIntegralType()))
319 return llvm::APSInt::isSameValue(Arg1.getAsIntegral(),
320 Arg2.getAsIntegral());
322 case TemplateArgument::Declaration:
323 return IsStructurallyEquivalent(Context, Arg1.getAsDecl(), Arg2.getAsDecl());
325 case TemplateArgument::NullPtr:
326 return true; // FIXME: Is this correct?
328 case TemplateArgument::Template:
329 return IsStructurallyEquivalent(Context, Arg1.getAsTemplate(),
330 Arg2.getAsTemplate());
332 case TemplateArgument::TemplateExpansion:
333 return IsStructurallyEquivalent(Context,
334 Arg1.getAsTemplateOrTemplatePattern(),
335 Arg2.getAsTemplateOrTemplatePattern());
337 case TemplateArgument::Expression:
338 return IsStructurallyEquivalent(Context, Arg1.getAsExpr(),
341 case TemplateArgument::Pack:
342 if (Arg1.pack_size() != Arg2.pack_size())
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]))
353 llvm_unreachable("Invalid template argument kind");
356 /// Determine structural equivalence for the common part of array
358 static bool IsArrayStructurallyEquivalent(StructuralEquivalenceContext &Context,
359 const ArrayType *Array1,
360 const ArrayType *Array2) {
361 if (!IsStructurallyEquivalent(Context, Array1->getElementType(),
362 Array2->getElementType()))
364 if (Array1->getSizeModifier() != Array2->getSizeModifier())
366 if (Array1->getIndexTypeQualifiers() != Array2->getIndexTypeQualifiers())
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.
375 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
376 FunctionType::ExtInfo EI1,
377 FunctionType::ExtInfo EI2) {
378 // Compatible functions must have compatible calling conventions.
379 if (EI1.getCC() != EI2.getCC())
382 // Regparm is part of the calling convention.
383 if (EI1.getHasRegParm() != EI2.getHasRegParm())
385 if (EI1.getRegParm() != EI2.getRegParm())
388 if (EI1.getProducesResult() != EI2.getProducesResult())
390 if (EI1.getNoCallerSavedRegs() != EI2.getNoCallerSavedRegs())
392 if (EI1.getNoCfCheck() != EI2.getNoCfCheck())
398 /// Check the equivalence of exception specifications.
399 static bool IsEquivalentExceptionSpec(StructuralEquivalenceContext &Context,
400 const FunctionProtoType *Proto1,
401 const FunctionProtoType *Proto2) {
403 auto Spec1 = Proto1->getExceptionSpecType();
404 auto Spec2 = Proto2->getExceptionSpecType();
406 if (isUnresolvedExceptionSpec(Spec1) || isUnresolvedExceptionSpec(Spec2))
411 if (Spec1 == EST_Dynamic) {
412 if (Proto1->getNumExceptions() != Proto2->getNumExceptions())
414 for (unsigned I = 0, N = Proto1->getNumExceptions(); I != N; ++I) {
415 if (!IsStructurallyEquivalent(Context, Proto1->getExceptionType(I),
416 Proto2->getExceptionType(I)))
419 } else if (isComputedNoexcept(Spec1)) {
420 if (!IsStructurallyEquivalent(Context, Proto1->getNoexceptExpr(),
421 Proto2->getNoexceptExpr()))
428 /// Determine structural equivalence of two types.
429 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
430 QualType T1, QualType T2) {
431 if (T1.isNull() || T2.isNull())
432 return T1.isNull() && T2.isNull();
434 QualType OrigT1 = T1;
435 QualType OrigT2 = T2;
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);
444 if (T1.getQualifiers() != T2.getQualifiers())
447 Type::TypeClass TC = T1->getTypeClass();
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;
464 // FIXME: Deal with Char_S/Char_U.
465 if (cast<BuiltinType>(T1)->getKind() != cast<BuiltinType>(T2)->getKind())
470 if (!IsStructurallyEquivalent(Context,
471 cast<ComplexType>(T1)->getElementType(),
472 cast<ComplexType>(T2)->getElementType()))
478 if (!IsStructurallyEquivalent(Context,
479 cast<AdjustedType>(T1)->getOriginalType(),
480 cast<AdjustedType>(T2)->getOriginalType()))
485 if (!IsStructurallyEquivalent(Context,
486 cast<PointerType>(T1)->getPointeeType(),
487 cast<PointerType>(T2)->getPointeeType()))
491 case Type::BlockPointer:
492 if (!IsStructurallyEquivalent(Context,
493 cast<BlockPointerType>(T1)->getPointeeType(),
494 cast<BlockPointerType>(T2)->getPointeeType()))
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())
504 if (Ref1->isInnerRef() != Ref2->isInnerRef())
506 if (!IsStructurallyEquivalent(Context, Ref1->getPointeeTypeAsWritten(),
507 Ref2->getPointeeTypeAsWritten()))
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()))
518 if (!IsStructurallyEquivalent(Context, QualType(MemPtr1->getClass(), 0),
519 QualType(MemPtr2->getClass(), 0)))
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()))
530 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
535 case Type::IncompleteArray:
536 if (!IsArrayStructurallyEquivalent(Context, cast<ArrayType>(T1),
537 cast<ArrayType>(T2)))
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()))
548 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
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()))
561 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
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()))
573 if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getPointeeType(),
574 DepAddressSpace2->getPointeeType()))
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()))
586 if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
587 Vec2->getElementType()))
592 case Type::DependentVector: {
593 const auto *Vec1 = cast<DependentVectorType>(T1);
594 const auto *Vec2 = cast<DependentVectorType>(T2);
595 if (Vec1->getVectorKind() != Vec2->getVectorKind())
597 if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
598 Vec2->getSizeExpr()))
600 if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
601 Vec2->getElementType()))
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()))
613 if (Vec1->getNumElements() != Vec2->getNumElements())
615 if (Vec1->getVectorKind() != Vec2->getVectorKind())
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
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()))
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())
648 case Type::FunctionProto: {
649 const auto *Proto1 = cast<FunctionProtoType>(T1);
650 const auto *Proto2 = cast<FunctionProtoType>(T2);
652 if (Proto1->getNumParams() != Proto2->getNumParams())
654 for (unsigned I = 0, N = Proto1->getNumParams(); I != N; ++I) {
655 if (!IsStructurallyEquivalent(Context, Proto1->getParamType(I),
656 Proto2->getParamType(I)))
659 if (Proto1->isVariadic() != Proto2->isVariadic())
662 if (Proto1->getMethodQuals() != Proto2->getMethodQuals())
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))
673 // Fall through to check the bits common with FunctionNoProtoType.
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()))
683 if (!IsStructurallyEquivalent(Context, Function1->getExtInfo(),
684 Function2->getExtInfo()))
689 case Type::UnresolvedUsing:
690 if (!IsStructurallyEquivalent(Context,
691 cast<UnresolvedUsingType>(T1)->getDecl(),
692 cast<UnresolvedUsingType>(T2)->getDecl()))
696 case Type::Attributed:
697 if (!IsStructurallyEquivalent(Context,
698 cast<AttributedType>(T1)->getModifiedType(),
699 cast<AttributedType>(T2)->getModifiedType()))
701 if (!IsStructurallyEquivalent(
702 Context, cast<AttributedType>(T1)->getEquivalentType(),
703 cast<AttributedType>(T2)->getEquivalentType()))
708 if (!IsStructurallyEquivalent(Context, cast<ParenType>(T1)->getInnerType(),
709 cast<ParenType>(T2)->getInnerType()))
713 case Type::MacroQualified:
714 if (!IsStructurallyEquivalent(
715 Context, cast<MacroQualifiedType>(T1)->getUnderlyingType(),
716 cast<MacroQualifiedType>(T2)->getUnderlyingType()))
721 if (!IsStructurallyEquivalent(Context, cast<TypedefType>(T1)->getDecl(),
722 cast<TypedefType>(T2)->getDecl()))
726 case Type::TypeOfExpr:
727 if (!IsStructurallyEquivalent(
728 Context, cast<TypeOfExprType>(T1)->getUnderlyingExpr(),
729 cast<TypeOfExprType>(T2)->getUnderlyingExpr()))
734 if (!IsStructurallyEquivalent(Context,
735 cast<TypeOfType>(T1)->getUnderlyingType(),
736 cast<TypeOfType>(T2)->getUnderlyingType()))
740 case Type::UnaryTransform:
741 if (!IsStructurallyEquivalent(
742 Context, cast<UnaryTransformType>(T1)->getUnderlyingType(),
743 cast<UnaryTransformType>(T2)->getUnderlyingType()))
748 if (!IsStructurallyEquivalent(Context,
749 cast<DecltypeType>(T1)->getUnderlyingExpr(),
750 cast<DecltypeType>(T2)->getUnderlyingExpr()))
755 auto *Auto1 = cast<AutoType>(T1);
756 auto *Auto2 = cast<AutoType>(T2);
757 if (!IsStructurallyEquivalent(Context, Auto1->getDeducedType(),
758 Auto2->getDeducedType()))
760 if (Auto1->isConstrained() != Auto2->isConstrained())
762 if (Auto1->isConstrained()) {
763 if (Auto1->getTypeConstraintConcept() !=
764 Auto2->getTypeConstraintConcept())
766 ArrayRef<TemplateArgument> Auto1Args =
767 Auto1->getTypeConstraintArguments();
768 ArrayRef<TemplateArgument> Auto2Args =
769 Auto2->getTypeConstraintArguments();
770 if (Auto1Args.size() != Auto2Args.size())
772 for (unsigned I = 0, N = Auto1Args.size(); I != N; ++I) {
773 if (!IsStructurallyEquivalent(Context, Auto1Args[I], Auto2Args[I]))
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()))
786 if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),
787 DT2->getDeducedType()))
794 if (!IsStructurallyEquivalent(Context, cast<TagType>(T1)->getDecl(),
795 cast<TagType>(T2)->getDecl()))
799 case Type::TemplateTypeParm: {
800 const auto *Parm1 = cast<TemplateTypeParmType>(T1);
801 const auto *Parm2 = cast<TemplateTypeParmType>(T2);
802 if (Parm1->getDepth() != Parm2->getDepth())
804 if (Parm1->getIndex() != Parm2->getIndex())
806 if (Parm1->isParameterPack() != Parm2->isParameterPack())
809 // Names of template type parameters are never significant.
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)))
820 if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),
821 Subst2->getReplacementType()))
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)))
833 if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),
834 Subst2->getArgumentPack()))
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()))
845 if (Spec1->getNumArgs() != Spec2->getNumArgs())
847 for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
848 if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
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())
861 if (!IsStructurallyEquivalent(Context, Elab1->getQualifier(),
862 Elab2->getQualifier()))
864 if (!IsStructurallyEquivalent(Context, Elab1->getNamedType(),
865 Elab2->getNamedType()))
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()))
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()))
886 if (!IsStructurallyEquivalent(Typename1->getIdentifier(),
887 Typename2->getIdentifier()))
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()))
899 if (!IsStructurallyEquivalent(Spec1->getIdentifier(),
900 Spec2->getIdentifier()))
902 if (Spec1->getNumArgs() != Spec2->getNumArgs())
904 for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
905 if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
912 case Type::PackExpansion:
913 if (!IsStructurallyEquivalent(Context,
914 cast<PackExpansionType>(T1)->getPattern(),
915 cast<PackExpansionType>(T2)->getPattern()))
919 case Type::ObjCInterface: {
920 const auto *Iface1 = cast<ObjCInterfaceType>(T1);
921 const auto *Iface2 = cast<ObjCInterfaceType>(T2);
922 if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),
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()))
934 if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
936 for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
937 if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
938 Obj2->getProtocol(I)))
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()))
950 if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
952 for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
953 if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
954 Obj2->getProtocol(I)))
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()))
970 if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(),
971 cast<AtomicType>(T2)->getValueType()))
976 if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(),
977 cast<PipeType>(T2)->getElementType()))
981 const auto *Int1 = cast<ExtIntType>(T1);
982 const auto *Int2 = cast<ExtIntType>(T2);
984 if (Int1->isUnsigned() != Int2->isUnsigned() ||
985 Int1->getNumBits() != Int2->getNumBits())
989 case Type::DependentExtInt: {
990 const auto *Int1 = cast<DependentExtIntType>(T1);
991 const auto *Int2 = cast<DependentExtIntType>(T2);
993 if (Int1->isUnsigned() != Int2->isUnsigned() ||
994 !IsStructurallyEquivalent(Context, Int1->getNumBitsExpr(),
995 Int2->getNumBitsExpr()))
1003 /// Determine structural equivalence of two fields.
1004 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1005 FieldDecl *Field1, FieldDecl *Field2) {
1006 const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
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
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);
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) {
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();
1035 if (!IsStructurallyEquivalent(Context, Field1->getType(),
1036 Field2->getType())) {
1037 if (Context.Complain) {
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();
1050 if (Field1->isBitField() != Field2->isBitField()) {
1051 if (Context.Complain) {
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();
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();
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);
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;
1096 /// Determine structural equivalence of two methods.
1097 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
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)
1114 // FIXME: Check for 'final'.
1116 if (auto *Constructor1 = dyn_cast<CXXConstructorDecl>(Method1)) {
1117 auto *Constructor2 = cast<CXXConstructorDecl>(Method2);
1118 if (!Constructor1->getExplicitSpecifier().isEquivalent(
1119 Constructor2->getExplicitSpecifier()))
1123 if (auto *Conversion1 = dyn_cast<CXXConversionDecl>(Method1)) {
1124 auto *Conversion2 = cast<CXXConversionDecl>(Method2);
1125 if (!Conversion1->getExplicitSpecifier().isEquivalent(
1126 Conversion2->getExplicitSpecifier()))
1128 if (!IsStructurallyEquivalent(Context, Conversion1->getConversionType(),
1129 Conversion2->getConversionType()))
1133 const IdentifierInfo *Name1 = Method1->getIdentifier();
1134 const IdentifierInfo *Name2 = Method2->getIdentifier();
1135 if (!::IsStructurallyEquivalent(Name1, Name2)) {
1137 // TODO: Names do not match, add warning like at check for FieldDecl.
1140 // Check the prototypes.
1141 if (!::IsStructurallyEquivalent(Context,
1142 Method1->getType(), Method2->getType()))
1148 /// Determine structural equivalence of two lambda classes.
1150 IsStructurallyEquivalentLambdas(StructuralEquivalenceContext &Context,
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()))
1161 /// Determine structural equivalence of two records.
1162 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
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();
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 =
1179 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(D1)) {
1180 if (Optional<unsigned> Index2 =
1181 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(
1183 if (*Index1 != *Index2)
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()))
1199 // Check that the template arguments are the same.
1200 if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())
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)))
1208 // If one is a class template specialization and the other is not, these
1209 // structures are different.
1210 else if (Spec1 || Spec2)
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
1216 D1 = D1->getDefinition();
1217 D2 = D2->getDefinition();
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.)
1226 if (Context.EqKind == StructuralEquivalenceKind::Minimal)
1227 if (D1->hasExternalLexicalStorage() || D2->hasExternalLexicalStorage())
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())
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);
1242 if (D1CXX->isLambda() != D2CXX->isLambda())
1244 if (D1CXX->isLambda()) {
1245 if (!IsStructurallyEquivalentLambdas(Context, D1CXX, D2CXX))
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();
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();
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();
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);
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);
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);
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);
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);
1375 if (!IsStructurallyEquivalent(Context, *Field1, *Field2))
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);
1394 /// Determine structural equivalence of two enums.
1395 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1396 EnumDecl *D1, EnumDecl *D2) {
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();
1405 EnumDecl::enumerator_iterator EC2 = D2->enumerator_begin(),
1406 EC2End = D2->enumerator_end();
1407 for (EnumDecl::enumerator_iterator EC1 = D1->enumerator_begin(),
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);
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);
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);
1456 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
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);
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);
1483 if (!IsStructurallyEquivalent(Context, Params1->getParam(I),
1484 Params2->getParam(I)))
1491 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1492 TemplateTypeParmDecl *D1,
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();
1509 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1510 NonTypeTemplateParmDecl *D1,
1511 NonTypeTemplateParmDecl *D2) {
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();
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)
1540 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1541 TemplateTemplateParmDecl *D1,
1542 TemplateTemplateParmDecl *D2) {
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();
1555 // Check template parameter lists.
1556 return IsStructurallyEquivalent(Context, D1->getTemplateParameters(),
1557 D2->getTemplateParameters());
1560 static bool IsTemplateDeclCommonStructurallyEquivalent(
1561 StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) {
1562 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1564 if (!D1->getIdentifier()) // Special name
1565 if (D1->getNameAsString() != D2->getNameAsString())
1567 return IsStructurallyEquivalent(Ctx, D1->getTemplateParameters(),
1568 D2->getTemplateParameters());
1571 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1572 ClassTemplateDecl *D1,
1573 ClassTemplateDecl *D2) {
1574 // Check template parameters.
1575 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1578 // Check the templated declaration.
1579 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
1580 D2->getTemplatedDecl());
1583 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1584 FunctionTemplateDecl *D1,
1585 FunctionTemplateDecl *D2) {
1586 // Check template parameters.
1587 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1590 // Check the templated declaration.
1591 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),
1592 D2->getTemplatedDecl()->getType());
1595 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1598 // Check template parameters.
1599 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1602 // Check the constraint expression.
1603 return IsStructurallyEquivalent(Context, D1->getConstraintExpr(),
1604 D2->getConstraintExpr());
1607 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1608 FriendDecl *D1, FriendDecl *D2) {
1609 if ((D1->getFriendType() && D2->getFriendDecl()) ||
1610 (D1->getFriendDecl() && D2->getFriendType())) {
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());
1623 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1624 FunctionDecl *D1, FunctionDecl *D2) {
1625 // FIXME: Consider checking for function attributes as well.
1626 if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))
1632 /// Determine structural equivalence of two declarations.
1633 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1634 Decl *D1, Decl *D2) {
1635 // FIXME: Check for known structural equivalences via a callback of some sort.
1637 D1 = D1->getCanonicalDecl();
1638 D2 = D2->getCanonicalDecl();
1639 std::pair<Decl *, Decl *> P{D1, D2};
1641 // Check whether we already know that these two declarations are not
1642 // structurally equivalent.
1643 if (Context.NonEquivalentDecls.count(P))
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;
1653 Context.DeclsToCheck.push(P);
1658 DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
1660 assert(Complain && "Not allowed to complain");
1662 FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics());
1663 LastDiagFromC2 = false;
1664 return FromCtx.getDiagnostics().Report(Loc, DiagID);
1667 DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,
1669 assert(Complain && "Not allowed to complain");
1670 if (!LastDiagFromC2)
1671 ToCtx.getDiagnostics().notePriorDiagnosticFrom(FromCtx.getDiagnostics());
1672 LastDiagFromC2 = true;
1673 return ToCtx.getDiagnostics().Report(Loc, DiagID);
1677 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) {
1678 ASTContext &Context = Anon->getASTContext();
1679 QualType AnonTy = Context.getRecordType(Anon);
1681 const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());
1686 for (const auto *D : Owner->noload_decls()) {
1687 const auto *F = dyn_cast<FieldDecl>(D);
1691 if (F->isAnonymousStructOrUnion()) {
1692 if (Context.hasSameType(F->getType(), AnonTy))
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();
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))
1719 unsigned StructuralEquivalenceContext::getApplicableDiagnostic(
1720 unsigned ErrorDiagnostic) {
1721 if (ErrorOnTagTypeMismatch)
1722 return ErrorDiagnostic;
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;
1762 llvm_unreachable("Diagnostic kind not handled in preceding switch");
1765 bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) {
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
1775 assert(DeclsToCheck.empty());
1776 assert(VisitedDecls.empty());
1778 if (!::IsStructurallyEquivalent(*this, D1, D2))
1784 bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
1785 assert(DeclsToCheck.empty());
1786 assert(VisitedDecls.empty());
1787 if (!::IsStructurallyEquivalent(*this, T1, T2))
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))
1799 if (Template1 && !IsStructurallyEquivalent(*this, Template1, Template2))
1802 // FIXME: Move check for identifier names into this function.
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))
1824 // Record/non-record mismatch.
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))
1840 // Enum/non-enum mismatch
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()))
1851 // Typedef/non-typedef mismatch.
1854 } else if (auto *ClassTemplate1 = dyn_cast<ClassTemplateDecl>(D1)) {
1855 if (auto *ClassTemplate2 = dyn_cast<ClassTemplateDecl>(D2)) {
1856 if (!::IsStructurallyEquivalent(*this, ClassTemplate1,
1860 // Class template/non-class-template mismatch.
1863 } else if (auto *FunctionTemplate1 = dyn_cast<FunctionTemplateDecl>(D1)) {
1864 if (auto *FunctionTemplate2 = dyn_cast<FunctionTemplateDecl>(D2)) {
1865 if (!::IsStructurallyEquivalent(*this, FunctionTemplate1,
1869 // Class template/non-class-template mismatch.
1872 } else if (auto *ConceptDecl1 = dyn_cast<ConceptDecl>(D1)) {
1873 if (auto *ConceptDecl2 = dyn_cast<ConceptDecl>(D2)) {
1874 if (!::IsStructurallyEquivalent(*this, ConceptDecl1, ConceptDecl2))
1877 // Concept/non-concept mismatch.
1880 } else if (auto *TTP1 = dyn_cast<TemplateTypeParmDecl>(D1)) {
1881 if (auto *TTP2 = dyn_cast<TemplateTypeParmDecl>(D2)) {
1882 if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1888 } else if (auto *NTTP1 = dyn_cast<NonTypeTemplateParmDecl>(D1)) {
1889 if (auto *NTTP2 = dyn_cast<NonTypeTemplateParmDecl>(D2)) {
1890 if (!::IsStructurallyEquivalent(*this, NTTP1, NTTP2))
1896 } else if (auto *TTP1 = dyn_cast<TemplateTemplateParmDecl>(D1)) {
1897 if (auto *TTP2 = dyn_cast<TemplateTemplateParmDecl>(D2)) {
1898 if (!::IsStructurallyEquivalent(*this, TTP1, TTP2))
1904 } else if (auto *MD1 = dyn_cast<CXXMethodDecl>(D1)) {
1905 if (auto *MD2 = dyn_cast<CXXMethodDecl>(D2)) {
1906 if (!::IsStructurallyEquivalent(*this, MD1, MD2))
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())
1917 if (FD1->getOverloadedOperator() != FD2->getOverloadedOperator())
1920 if (!::IsStructurallyEquivalent(FD1->getIdentifier(),
1921 FD2->getIdentifier()))
1923 if (!::IsStructurallyEquivalent(*this, FD1, FD2))
1929 } else if (FriendDecl *FrD1 = dyn_cast<FriendDecl>(D1)) {
1930 if (FriendDecl *FrD2 = dyn_cast<FriendDecl>(D2)) {
1931 if (!::IsStructurallyEquivalent(*this, FrD1, FrD2))
1942 bool StructuralEquivalenceContext::Finish() {
1943 while (!DeclsToCheck.empty()) {
1944 // Check the next declaration.
1945 std::pair<Decl *, Decl *> P = DeclsToCheck.front();
1949 Decl *D2 = P.second;
1952 CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);
1955 // Note that these two declarations are not equivalent (and we already
1957 NonEquivalentDecls.insert(P);