1 //===- ASTStructuralEquivalence.cpp ---------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implement StructuralEquivalenceContext class and helper functions
10 // for layout matching.
11 //
12 // The structural equivalence check could have been implemented as a parallel
13 // BFS on a pair of graphs. That must have been the original approach at the
14 // beginning.
15 // Let's consider this simple BFS algorithm from the `s` source:
16 // ```
17 // void bfs(Graph G, int s)
18 // {
19 // Queue<Integer> queue = new Queue<Integer>();
20 // marked[s] = true; // Mark the source
21 // queue.enqueue(s); // and put it on the queue.
22 // while (!q.isEmpty()) {
23 // int v = queue.dequeue(); // Remove next vertex from the queue.
24 // for (int w : G.adj(v))
25 // if (!marked[w]) // For every unmarked adjacent vertex,
26 // {
27 // marked[w] = true;
28 // queue.enqueue(w);
29 // }
30 // }
31 // }
32 // ```
33 // Indeed, it has it's queue, which holds pairs of nodes, one from each graph,
34 // this is the `DeclsToCheck` member. `VisitedDecls` plays the role of the
35 // marking (`marked`) functionality above, we use it to check whether we've
36 // already seen a pair of nodes.
37 //
38 // We put in the elements into the queue only in the toplevel decl check
39 // function:
40 // ```
41 // static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
42 // Decl *D1, Decl *D2);
43 // ```
44 // The `while` loop where we iterate over the children is implemented in
45 // `Finish()`. And `Finish` is called only from the two **member** functions
46 // which check the equivalency of two Decls or two Types. ASTImporter (and
47 // other clients) call only these functions.
48 //
49 // The `static` implementation functions are called from `Finish`, these push
50 // the children nodes to the queue via `static bool
51 // IsStructurallyEquivalent(StructuralEquivalenceContext &Context, Decl *D1,
52 // Decl *D2)`. So far so good, this is almost like the BFS. However, if we
53 // let a static implementation function to call `Finish` via another **member**
54 // function that means we end up with two nested while loops each of them
55 // working on the same queue. This is wrong and nobody can reason about it's
56 // doing. Thus, static implementation functions must not call the **member**
57 // functions.
58 //
59 //===----------------------------------------------------------------------===//
60
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/DeclOpenMP.h"
70 #include "clang/AST/DeclTemplate.h"
71 #include "clang/AST/ExprCXX.h"
72 #include "clang/AST/ExprConcepts.h"
73 #include "clang/AST/ExprObjC.h"
74 #include "clang/AST/ExprOpenMP.h"
75 #include "clang/AST/NestedNameSpecifier.h"
76 #include "clang/AST/StmtObjC.h"
77 #include "clang/AST/StmtOpenMP.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"
92 #include <cassert>
93 #include <utility>
94
95 using namespace clang;
96
97 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
98 QualType T1, QualType T2);
99 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
100 Decl *D1, Decl *D2);
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);
109
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,const DeclarationName Name1,const DeclarationName Name2)110 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
111 const DeclarationName Name1,
112 const DeclarationName Name2) {
113 if (Name1.getNameKind() != Name2.getNameKind())
114 return false;
115
116 switch (Name1.getNameKind()) {
117
118 case DeclarationName::Identifier:
119 return IsStructurallyEquivalent(Name1.getAsIdentifierInfo(),
120 Name2.getAsIdentifierInfo());
121
122 case DeclarationName::CXXConstructorName:
123 case DeclarationName::CXXDestructorName:
124 case DeclarationName::CXXConversionFunctionName:
125 return IsStructurallyEquivalent(Context, Name1.getCXXNameType(),
126 Name2.getCXXNameType());
127
128 case DeclarationName::CXXDeductionGuideName: {
129 if (!IsStructurallyEquivalent(
130 Context, Name1.getCXXDeductionGuideTemplate()->getDeclName(),
131 Name2.getCXXDeductionGuideTemplate()->getDeclName()))
132 return false;
133 return IsStructurallyEquivalent(Context,
134 Name1.getCXXDeductionGuideTemplate(),
135 Name2.getCXXDeductionGuideTemplate());
136 }
137
138 case DeclarationName::CXXOperatorName:
139 return Name1.getCXXOverloadedOperator() == Name2.getCXXOverloadedOperator();
140
141 case DeclarationName::CXXLiteralOperatorName:
142 return IsStructurallyEquivalent(Name1.getCXXLiteralIdentifier(),
143 Name2.getCXXLiteralIdentifier());
144
145 case DeclarationName::CXXUsingDirective:
146 return true; // FIXME When do we consider two using directives equal?
147
148 case DeclarationName::ObjCZeroArgSelector:
149 case DeclarationName::ObjCOneArgSelector:
150 case DeclarationName::ObjCMultiArgSelector:
151 return true; // FIXME
152 }
153
154 llvm_unreachable("Unhandled kind of DeclarationName");
155 return true;
156 }
157
158 namespace {
159 /// Encapsulates Stmt comparison logic.
160 class StmtComparer {
161 StructuralEquivalenceContext &Context;
162
163 // IsStmtEquivalent overloads. Each overload compares a specific statement
164 // and only has to compare the data that is specific to the specific statement
165 // class. Should only be called from TraverseStmt.
166
IsStmtEquivalent(const AddrLabelExpr * E1,const AddrLabelExpr * E2)167 bool IsStmtEquivalent(const AddrLabelExpr *E1, const AddrLabelExpr *E2) {
168 return IsStructurallyEquivalent(Context, E1->getLabel(), E2->getLabel());
169 }
170
IsStmtEquivalent(const AtomicExpr * E1,const AtomicExpr * E2)171 bool IsStmtEquivalent(const AtomicExpr *E1, const AtomicExpr *E2) {
172 return E1->getOp() == E2->getOp();
173 }
174
IsStmtEquivalent(const BinaryOperator * E1,const BinaryOperator * E2)175 bool IsStmtEquivalent(const BinaryOperator *E1, const BinaryOperator *E2) {
176 return E1->getOpcode() == E2->getOpcode();
177 }
178
IsStmtEquivalent(const CallExpr * E1,const CallExpr * E2)179 bool IsStmtEquivalent(const CallExpr *E1, const CallExpr *E2) {
180 // FIXME: IsStructurallyEquivalent requires non-const Decls.
181 Decl *Callee1 = const_cast<Decl *>(E1->getCalleeDecl());
182 Decl *Callee2 = const_cast<Decl *>(E2->getCalleeDecl());
183
184 // Compare whether both calls know their callee.
185 if (static_cast<bool>(Callee1) != static_cast<bool>(Callee2))
186 return false;
187
188 // Both calls have no callee, so nothing to do.
189 if (!static_cast<bool>(Callee1))
190 return true;
191
192 assert(Callee2);
193 return IsStructurallyEquivalent(Context, Callee1, Callee2);
194 }
195
IsStmtEquivalent(const CharacterLiteral * E1,const CharacterLiteral * E2)196 bool IsStmtEquivalent(const CharacterLiteral *E1,
197 const CharacterLiteral *E2) {
198 return E1->getValue() == E2->getValue() && E1->getKind() == E2->getKind();
199 }
200
IsStmtEquivalent(const ChooseExpr * E1,const ChooseExpr * E2)201 bool IsStmtEquivalent(const ChooseExpr *E1, const ChooseExpr *E2) {
202 return true; // Semantics only depend on children.
203 }
204
IsStmtEquivalent(const CompoundStmt * E1,const CompoundStmt * E2)205 bool IsStmtEquivalent(const CompoundStmt *E1, const CompoundStmt *E2) {
206 // Number of children is actually checked by the generic children comparison
207 // code, but a CompoundStmt is one of the few statements where the number of
208 // children frequently differs and the number of statements is also always
209 // precomputed. Directly comparing the number of children here is thus
210 // just an optimization.
211 return E1->size() == E2->size();
212 }
213
IsStmtEquivalent(const DependentScopeDeclRefExpr * DE1,const DependentScopeDeclRefExpr * DE2)214 bool IsStmtEquivalent(const DependentScopeDeclRefExpr *DE1,
215 const DependentScopeDeclRefExpr *DE2) {
216 if (!IsStructurallyEquivalent(Context, DE1->getDeclName(),
217 DE2->getDeclName()))
218 return false;
219 return IsStructurallyEquivalent(Context, DE1->getQualifier(),
220 DE2->getQualifier());
221 }
222
IsStmtEquivalent(const Expr * E1,const Expr * E2)223 bool IsStmtEquivalent(const Expr *E1, const Expr *E2) {
224 return IsStructurallyEquivalent(Context, E1->getType(), E2->getType());
225 }
226
IsStmtEquivalent(const ExpressionTraitExpr * E1,const ExpressionTraitExpr * E2)227 bool IsStmtEquivalent(const ExpressionTraitExpr *E1,
228 const ExpressionTraitExpr *E2) {
229 return E1->getTrait() == E2->getTrait() && E1->getValue() == E2->getValue();
230 }
231
IsStmtEquivalent(const FloatingLiteral * E1,const FloatingLiteral * E2)232 bool IsStmtEquivalent(const FloatingLiteral *E1, const FloatingLiteral *E2) {
233 return E1->isExact() == E2->isExact() && E1->getValue() == E2->getValue();
234 }
235
IsStmtEquivalent(const GenericSelectionExpr * E1,const GenericSelectionExpr * E2)236 bool IsStmtEquivalent(const GenericSelectionExpr *E1,
237 const GenericSelectionExpr *E2) {
238 for (auto Pair : zip_longest(E1->getAssocTypeSourceInfos(),
239 E2->getAssocTypeSourceInfos())) {
240 Optional<TypeSourceInfo *> Child1 = std::get<0>(Pair);
241 Optional<TypeSourceInfo *> Child2 = std::get<1>(Pair);
242 // Skip this case if there are a different number of associated types.
243 if (!Child1 || !Child2)
244 return false;
245
246 if (!IsStructurallyEquivalent(Context, (*Child1)->getType(),
247 (*Child2)->getType()))
248 return false;
249 }
250
251 return true;
252 }
253
IsStmtEquivalent(const ImplicitCastExpr * CastE1,const ImplicitCastExpr * CastE2)254 bool IsStmtEquivalent(const ImplicitCastExpr *CastE1,
255 const ImplicitCastExpr *CastE2) {
256 return IsStructurallyEquivalent(Context, CastE1->getType(),
257 CastE2->getType());
258 }
259
IsStmtEquivalent(const IntegerLiteral * E1,const IntegerLiteral * E2)260 bool IsStmtEquivalent(const IntegerLiteral *E1, const IntegerLiteral *E2) {
261 return E1->getValue() == E2->getValue();
262 }
263
IsStmtEquivalent(const MemberExpr * E1,const MemberExpr * E2)264 bool IsStmtEquivalent(const MemberExpr *E1, const MemberExpr *E2) {
265 return IsStructurallyEquivalent(Context, E1->getFoundDecl(),
266 E2->getFoundDecl());
267 }
268
IsStmtEquivalent(const ObjCStringLiteral * E1,const ObjCStringLiteral * E2)269 bool IsStmtEquivalent(const ObjCStringLiteral *E1,
270 const ObjCStringLiteral *E2) {
271 // Just wraps a StringLiteral child.
272 return true;
273 }
274
IsStmtEquivalent(const Stmt * S1,const Stmt * S2)275 bool IsStmtEquivalent(const Stmt *S1, const Stmt *S2) { return true; }
276
IsStmtEquivalent(const SourceLocExpr * E1,const SourceLocExpr * E2)277 bool IsStmtEquivalent(const SourceLocExpr *E1, const SourceLocExpr *E2) {
278 return E1->getIdentKind() == E2->getIdentKind();
279 }
280
IsStmtEquivalent(const StmtExpr * E1,const StmtExpr * E2)281 bool IsStmtEquivalent(const StmtExpr *E1, const StmtExpr *E2) {
282 return E1->getTemplateDepth() == E2->getTemplateDepth();
283 }
284
IsStmtEquivalent(const StringLiteral * E1,const StringLiteral * E2)285 bool IsStmtEquivalent(const StringLiteral *E1, const StringLiteral *E2) {
286 return E1->getBytes() == E2->getBytes();
287 }
288
IsStmtEquivalent(const SubstNonTypeTemplateParmExpr * E1,const SubstNonTypeTemplateParmExpr * E2)289 bool IsStmtEquivalent(const SubstNonTypeTemplateParmExpr *E1,
290 const SubstNonTypeTemplateParmExpr *E2) {
291 return IsStructurallyEquivalent(Context, E1->getParameter(),
292 E2->getParameter());
293 }
294
IsStmtEquivalent(const SubstNonTypeTemplateParmPackExpr * E1,const SubstNonTypeTemplateParmPackExpr * E2)295 bool IsStmtEquivalent(const SubstNonTypeTemplateParmPackExpr *E1,
296 const SubstNonTypeTemplateParmPackExpr *E2) {
297 return IsStructurallyEquivalent(Context, E1->getArgumentPack(),
298 E2->getArgumentPack());
299 }
300
IsStmtEquivalent(const TypeTraitExpr * E1,const TypeTraitExpr * E2)301 bool IsStmtEquivalent(const TypeTraitExpr *E1, const TypeTraitExpr *E2) {
302 if (E1->getTrait() != E2->getTrait())
303 return false;
304
305 for (auto Pair : zip_longest(E1->getArgs(), E2->getArgs())) {
306 Optional<TypeSourceInfo *> Child1 = std::get<0>(Pair);
307 Optional<TypeSourceInfo *> Child2 = std::get<1>(Pair);
308 // Different number of args.
309 if (!Child1 || !Child2)
310 return false;
311
312 if (!IsStructurallyEquivalent(Context, (*Child1)->getType(),
313 (*Child2)->getType()))
314 return false;
315 }
316 return true;
317 }
318
IsStmtEquivalent(const UnaryExprOrTypeTraitExpr * E1,const UnaryExprOrTypeTraitExpr * E2)319 bool IsStmtEquivalent(const UnaryExprOrTypeTraitExpr *E1,
320 const UnaryExprOrTypeTraitExpr *E2) {
321 if (E1->getKind() != E2->getKind())
322 return false;
323 return IsStructurallyEquivalent(Context, E1->getTypeOfArgument(),
324 E2->getTypeOfArgument());
325 }
326
IsStmtEquivalent(const UnaryOperator * E1,const UnaryOperator * E2)327 bool IsStmtEquivalent(const UnaryOperator *E1, const UnaryOperator *E2) {
328 return E1->getOpcode() == E2->getOpcode();
329 }
330
IsStmtEquivalent(const VAArgExpr * E1,const VAArgExpr * E2)331 bool IsStmtEquivalent(const VAArgExpr *E1, const VAArgExpr *E2) {
332 // Semantics only depend on children.
333 return true;
334 }
335
336 /// End point of the traversal chain.
TraverseStmt(const Stmt * S1,const Stmt * S2)337 bool TraverseStmt(const Stmt *S1, const Stmt *S2) { return true; }
338
339 // Create traversal methods that traverse the class hierarchy and return
340 // the accumulated result of the comparison. Each TraverseStmt overload
341 // calls the TraverseStmt overload of the parent class. For example,
342 // the TraverseStmt overload for 'BinaryOperator' calls the TraverseStmt
343 // overload of 'Expr' which then calls the overload for 'Stmt'.
344 #define STMT(CLASS, PARENT) \
345 bool TraverseStmt(const CLASS *S1, const CLASS *S2) { \
346 if (!TraverseStmt(static_cast<const PARENT *>(S1), \
347 static_cast<const PARENT *>(S2))) \
348 return false; \
349 return IsStmtEquivalent(S1, S2); \
350 }
351 #include "clang/AST/StmtNodes.inc"
352
353 public:
StmtComparer(StructuralEquivalenceContext & C)354 StmtComparer(StructuralEquivalenceContext &C) : Context(C) {}
355
356 /// Determine whether two statements are equivalent. The statements have to
357 /// be of the same kind. The children of the statements and their properties
358 /// are not compared by this function.
IsEquivalent(const Stmt * S1,const Stmt * S2)359 bool IsEquivalent(const Stmt *S1, const Stmt *S2) {
360 if (S1->getStmtClass() != S2->getStmtClass())
361 return false;
362
363 // Each TraverseStmt walks the class hierarchy from the leaf class to
364 // the root class 'Stmt' (e.g. 'BinaryOperator' -> 'Expr' -> 'Stmt'). Cast
365 // the Stmt we have here to its specific subclass so that we call the
366 // overload that walks the whole class hierarchy from leaf to root (e.g.,
367 // cast to 'BinaryOperator' so that 'Expr' and 'Stmt' is traversed).
368 switch (S1->getStmtClass()) {
369 case Stmt::NoStmtClass:
370 llvm_unreachable("Can't traverse NoStmtClass");
371 #define STMT(CLASS, PARENT) \
372 case Stmt::StmtClass::CLASS##Class: \
373 return TraverseStmt(static_cast<const CLASS *>(S1), \
374 static_cast<const CLASS *>(S2));
375 #define ABSTRACT_STMT(S)
376 #include "clang/AST/StmtNodes.inc"
377 }
378 llvm_unreachable("Invalid statement kind");
379 }
380 };
381 } // namespace
382
383 /// Determine structural equivalence of two statements.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,const Stmt * S1,const Stmt * S2)384 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
385 const Stmt *S1, const Stmt *S2) {
386 if (!S1 || !S2)
387 return S1 == S2;
388
389 // Compare the statements itself.
390 StmtComparer Comparer(Context);
391 if (!Comparer.IsEquivalent(S1, S2))
392 return false;
393
394 // Iterate over the children of both statements and also compare them.
395 for (auto Pair : zip_longest(S1->children(), S2->children())) {
396 Optional<const Stmt *> Child1 = std::get<0>(Pair);
397 Optional<const Stmt *> Child2 = std::get<1>(Pair);
398 // One of the statements has a different amount of children than the other,
399 // so the statements can't be equivalent.
400 if (!Child1 || !Child2)
401 return false;
402 if (!IsStructurallyEquivalent(Context, *Child1, *Child2))
403 return false;
404 }
405 return true;
406 }
407
408 /// Determine whether two identifiers are equivalent.
IsStructurallyEquivalent(const IdentifierInfo * Name1,const IdentifierInfo * Name2)409 static bool IsStructurallyEquivalent(const IdentifierInfo *Name1,
410 const IdentifierInfo *Name2) {
411 if (!Name1 || !Name2)
412 return Name1 == Name2;
413
414 return Name1->getName() == Name2->getName();
415 }
416
417 /// Determine whether two nested-name-specifiers are equivalent.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,NestedNameSpecifier * NNS1,NestedNameSpecifier * NNS2)418 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
419 NestedNameSpecifier *NNS1,
420 NestedNameSpecifier *NNS2) {
421 if (NNS1->getKind() != NNS2->getKind())
422 return false;
423
424 NestedNameSpecifier *Prefix1 = NNS1->getPrefix(),
425 *Prefix2 = NNS2->getPrefix();
426 if ((bool)Prefix1 != (bool)Prefix2)
427 return false;
428
429 if (Prefix1)
430 if (!IsStructurallyEquivalent(Context, Prefix1, Prefix2))
431 return false;
432
433 switch (NNS1->getKind()) {
434 case NestedNameSpecifier::Identifier:
435 return IsStructurallyEquivalent(NNS1->getAsIdentifier(),
436 NNS2->getAsIdentifier());
437 case NestedNameSpecifier::Namespace:
438 return IsStructurallyEquivalent(Context, NNS1->getAsNamespace(),
439 NNS2->getAsNamespace());
440 case NestedNameSpecifier::NamespaceAlias:
441 return IsStructurallyEquivalent(Context, NNS1->getAsNamespaceAlias(),
442 NNS2->getAsNamespaceAlias());
443 case NestedNameSpecifier::TypeSpec:
444 case NestedNameSpecifier::TypeSpecWithTemplate:
445 return IsStructurallyEquivalent(Context, QualType(NNS1->getAsType(), 0),
446 QualType(NNS2->getAsType(), 0));
447 case NestedNameSpecifier::Global:
448 return true;
449 case NestedNameSpecifier::Super:
450 return IsStructurallyEquivalent(Context, NNS1->getAsRecordDecl(),
451 NNS2->getAsRecordDecl());
452 }
453 return false;
454 }
455
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,const TemplateName & N1,const TemplateName & N2)456 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
457 const TemplateName &N1,
458 const TemplateName &N2) {
459 TemplateDecl *TemplateDeclN1 = N1.getAsTemplateDecl();
460 TemplateDecl *TemplateDeclN2 = N2.getAsTemplateDecl();
461 if (TemplateDeclN1 && TemplateDeclN2) {
462 if (!IsStructurallyEquivalent(Context, TemplateDeclN1, TemplateDeclN2))
463 return false;
464 // If the kind is different we compare only the template decl.
465 if (N1.getKind() != N2.getKind())
466 return true;
467 } else if (TemplateDeclN1 || TemplateDeclN2)
468 return false;
469 else if (N1.getKind() != N2.getKind())
470 return false;
471
472 // Check for special case incompatibilities.
473 switch (N1.getKind()) {
474
475 case TemplateName::OverloadedTemplate: {
476 OverloadedTemplateStorage *OS1 = N1.getAsOverloadedTemplate(),
477 *OS2 = N2.getAsOverloadedTemplate();
478 OverloadedTemplateStorage::iterator I1 = OS1->begin(), I2 = OS2->begin(),
479 E1 = OS1->end(), E2 = OS2->end();
480 for (; I1 != E1 && I2 != E2; ++I1, ++I2)
481 if (!IsStructurallyEquivalent(Context, *I1, *I2))
482 return false;
483 return I1 == E1 && I2 == E2;
484 }
485
486 case TemplateName::AssumedTemplate: {
487 AssumedTemplateStorage *TN1 = N1.getAsAssumedTemplateName(),
488 *TN2 = N1.getAsAssumedTemplateName();
489 return TN1->getDeclName() == TN2->getDeclName();
490 }
491
492 case TemplateName::DependentTemplate: {
493 DependentTemplateName *DN1 = N1.getAsDependentTemplateName(),
494 *DN2 = N2.getAsDependentTemplateName();
495 if (!IsStructurallyEquivalent(Context, DN1->getQualifier(),
496 DN2->getQualifier()))
497 return false;
498 if (DN1->isIdentifier() && DN2->isIdentifier())
499 return IsStructurallyEquivalent(DN1->getIdentifier(),
500 DN2->getIdentifier());
501 else if (DN1->isOverloadedOperator() && DN2->isOverloadedOperator())
502 return DN1->getOperator() == DN2->getOperator();
503 return false;
504 }
505
506 case TemplateName::SubstTemplateTemplateParmPack: {
507 SubstTemplateTemplateParmPackStorage
508 *P1 = N1.getAsSubstTemplateTemplateParmPack(),
509 *P2 = N2.getAsSubstTemplateTemplateParmPack();
510 return IsStructurallyEquivalent(Context, P1->getArgumentPack(),
511 P2->getArgumentPack()) &&
512 IsStructurallyEquivalent(Context, P1->getParameterPack(),
513 P2->getParameterPack());
514 }
515
516 case TemplateName::Template:
517 case TemplateName::QualifiedTemplate:
518 case TemplateName::SubstTemplateTemplateParm:
519 // It is sufficient to check value of getAsTemplateDecl.
520 break;
521
522 }
523
524 return true;
525 }
526
527 /// Determine whether two template arguments are equivalent.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,const TemplateArgument & Arg1,const TemplateArgument & Arg2)528 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
529 const TemplateArgument &Arg1,
530 const TemplateArgument &Arg2) {
531 if (Arg1.getKind() != Arg2.getKind())
532 return false;
533
534 switch (Arg1.getKind()) {
535 case TemplateArgument::Null:
536 return true;
537
538 case TemplateArgument::Type:
539 return IsStructurallyEquivalent(Context, Arg1.getAsType(), Arg2.getAsType());
540
541 case TemplateArgument::Integral:
542 if (!IsStructurallyEquivalent(Context, Arg1.getIntegralType(),
543 Arg2.getIntegralType()))
544 return false;
545
546 return llvm::APSInt::isSameValue(Arg1.getAsIntegral(),
547 Arg2.getAsIntegral());
548
549 case TemplateArgument::Declaration:
550 return IsStructurallyEquivalent(Context, Arg1.getAsDecl(), Arg2.getAsDecl());
551
552 case TemplateArgument::NullPtr:
553 return true; // FIXME: Is this correct?
554
555 case TemplateArgument::Template:
556 return IsStructurallyEquivalent(Context, Arg1.getAsTemplate(),
557 Arg2.getAsTemplate());
558
559 case TemplateArgument::TemplateExpansion:
560 return IsStructurallyEquivalent(Context,
561 Arg1.getAsTemplateOrTemplatePattern(),
562 Arg2.getAsTemplateOrTemplatePattern());
563
564 case TemplateArgument::Expression:
565 return IsStructurallyEquivalent(Context, Arg1.getAsExpr(),
566 Arg2.getAsExpr());
567
568 case TemplateArgument::Pack:
569 if (Arg1.pack_size() != Arg2.pack_size())
570 return false;
571
572 for (unsigned I = 0, N = Arg1.pack_size(); I != N; ++I)
573 if (!IsStructurallyEquivalent(Context, Arg1.pack_begin()[I],
574 Arg2.pack_begin()[I]))
575 return false;
576
577 return true;
578 }
579
580 llvm_unreachable("Invalid template argument kind");
581 }
582
583 /// Determine structural equivalence for the common part of array
584 /// types.
IsArrayStructurallyEquivalent(StructuralEquivalenceContext & Context,const ArrayType * Array1,const ArrayType * Array2)585 static bool IsArrayStructurallyEquivalent(StructuralEquivalenceContext &Context,
586 const ArrayType *Array1,
587 const ArrayType *Array2) {
588 if (!IsStructurallyEquivalent(Context, Array1->getElementType(),
589 Array2->getElementType()))
590 return false;
591 if (Array1->getSizeModifier() != Array2->getSizeModifier())
592 return false;
593 if (Array1->getIndexTypeQualifiers() != Array2->getIndexTypeQualifiers())
594 return false;
595
596 return true;
597 }
598
599 /// Determine structural equivalence based on the ExtInfo of functions. This
600 /// is inspired by ASTContext::mergeFunctionTypes(), we compare calling
601 /// conventions bits but must not compare some other bits.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,FunctionType::ExtInfo EI1,FunctionType::ExtInfo EI2)602 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
603 FunctionType::ExtInfo EI1,
604 FunctionType::ExtInfo EI2) {
605 // Compatible functions must have compatible calling conventions.
606 if (EI1.getCC() != EI2.getCC())
607 return false;
608
609 // Regparm is part of the calling convention.
610 if (EI1.getHasRegParm() != EI2.getHasRegParm())
611 return false;
612 if (EI1.getRegParm() != EI2.getRegParm())
613 return false;
614
615 if (EI1.getProducesResult() != EI2.getProducesResult())
616 return false;
617 if (EI1.getNoCallerSavedRegs() != EI2.getNoCallerSavedRegs())
618 return false;
619 if (EI1.getNoCfCheck() != EI2.getNoCfCheck())
620 return false;
621
622 return true;
623 }
624
625 /// Check the equivalence of exception specifications.
IsEquivalentExceptionSpec(StructuralEquivalenceContext & Context,const FunctionProtoType * Proto1,const FunctionProtoType * Proto2)626 static bool IsEquivalentExceptionSpec(StructuralEquivalenceContext &Context,
627 const FunctionProtoType *Proto1,
628 const FunctionProtoType *Proto2) {
629
630 auto Spec1 = Proto1->getExceptionSpecType();
631 auto Spec2 = Proto2->getExceptionSpecType();
632
633 if (isUnresolvedExceptionSpec(Spec1) || isUnresolvedExceptionSpec(Spec2))
634 return true;
635
636 if (Spec1 != Spec2)
637 return false;
638 if (Spec1 == EST_Dynamic) {
639 if (Proto1->getNumExceptions() != Proto2->getNumExceptions())
640 return false;
641 for (unsigned I = 0, N = Proto1->getNumExceptions(); I != N; ++I) {
642 if (!IsStructurallyEquivalent(Context, Proto1->getExceptionType(I),
643 Proto2->getExceptionType(I)))
644 return false;
645 }
646 } else if (isComputedNoexcept(Spec1)) {
647 if (!IsStructurallyEquivalent(Context, Proto1->getNoexceptExpr(),
648 Proto2->getNoexceptExpr()))
649 return false;
650 }
651
652 return true;
653 }
654
655 /// Determine structural equivalence of two types.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,QualType T1,QualType T2)656 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
657 QualType T1, QualType T2) {
658 if (T1.isNull() || T2.isNull())
659 return T1.isNull() && T2.isNull();
660
661 QualType OrigT1 = T1;
662 QualType OrigT2 = T2;
663
664 if (!Context.StrictTypeSpelling) {
665 // We aren't being strict about token-to-token equivalence of types,
666 // so map down to the canonical type.
667 T1 = Context.FromCtx.getCanonicalType(T1);
668 T2 = Context.ToCtx.getCanonicalType(T2);
669 }
670
671 if (T1.getQualifiers() != T2.getQualifiers())
672 return false;
673
674 Type::TypeClass TC = T1->getTypeClass();
675
676 if (T1->getTypeClass() != T2->getTypeClass()) {
677 // Compare function types with prototypes vs. without prototypes as if
678 // both did not have prototypes.
679 if (T1->getTypeClass() == Type::FunctionProto &&
680 T2->getTypeClass() == Type::FunctionNoProto)
681 TC = Type::FunctionNoProto;
682 else if (T1->getTypeClass() == Type::FunctionNoProto &&
683 T2->getTypeClass() == Type::FunctionProto)
684 TC = Type::FunctionNoProto;
685 else
686 return false;
687 }
688
689 switch (TC) {
690 case Type::Builtin:
691 // FIXME: Deal with Char_S/Char_U.
692 if (cast<BuiltinType>(T1)->getKind() != cast<BuiltinType>(T2)->getKind())
693 return false;
694 break;
695
696 case Type::Complex:
697 if (!IsStructurallyEquivalent(Context,
698 cast<ComplexType>(T1)->getElementType(),
699 cast<ComplexType>(T2)->getElementType()))
700 return false;
701 break;
702
703 case Type::Adjusted:
704 case Type::Decayed:
705 if (!IsStructurallyEquivalent(Context,
706 cast<AdjustedType>(T1)->getOriginalType(),
707 cast<AdjustedType>(T2)->getOriginalType()))
708 return false;
709 break;
710
711 case Type::Pointer:
712 if (!IsStructurallyEquivalent(Context,
713 cast<PointerType>(T1)->getPointeeType(),
714 cast<PointerType>(T2)->getPointeeType()))
715 return false;
716 break;
717
718 case Type::BlockPointer:
719 if (!IsStructurallyEquivalent(Context,
720 cast<BlockPointerType>(T1)->getPointeeType(),
721 cast<BlockPointerType>(T2)->getPointeeType()))
722 return false;
723 break;
724
725 case Type::LValueReference:
726 case Type::RValueReference: {
727 const auto *Ref1 = cast<ReferenceType>(T1);
728 const auto *Ref2 = cast<ReferenceType>(T2);
729 if (Ref1->isSpelledAsLValue() != Ref2->isSpelledAsLValue())
730 return false;
731 if (Ref1->isInnerRef() != Ref2->isInnerRef())
732 return false;
733 if (!IsStructurallyEquivalent(Context, Ref1->getPointeeTypeAsWritten(),
734 Ref2->getPointeeTypeAsWritten()))
735 return false;
736 break;
737 }
738
739 case Type::MemberPointer: {
740 const auto *MemPtr1 = cast<MemberPointerType>(T1);
741 const auto *MemPtr2 = cast<MemberPointerType>(T2);
742 if (!IsStructurallyEquivalent(Context, MemPtr1->getPointeeType(),
743 MemPtr2->getPointeeType()))
744 return false;
745 if (!IsStructurallyEquivalent(Context, QualType(MemPtr1->getClass(), 0),
746 QualType(MemPtr2->getClass(), 0)))
747 return false;
748 break;
749 }
750
751 case Type::ConstantArray: {
752 const auto *Array1 = cast<ConstantArrayType>(T1);
753 const auto *Array2 = cast<ConstantArrayType>(T2);
754 if (!llvm::APInt::isSameValue(Array1->getSize(), Array2->getSize()))
755 return false;
756
757 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
758 return false;
759 break;
760 }
761
762 case Type::IncompleteArray:
763 if (!IsArrayStructurallyEquivalent(Context, cast<ArrayType>(T1),
764 cast<ArrayType>(T2)))
765 return false;
766 break;
767
768 case Type::VariableArray: {
769 const auto *Array1 = cast<VariableArrayType>(T1);
770 const auto *Array2 = cast<VariableArrayType>(T2);
771 if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
772 Array2->getSizeExpr()))
773 return false;
774
775 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
776 return false;
777
778 break;
779 }
780
781 case Type::DependentSizedArray: {
782 const auto *Array1 = cast<DependentSizedArrayType>(T1);
783 const auto *Array2 = cast<DependentSizedArrayType>(T2);
784 if (!IsStructurallyEquivalent(Context, Array1->getSizeExpr(),
785 Array2->getSizeExpr()))
786 return false;
787
788 if (!IsArrayStructurallyEquivalent(Context, Array1, Array2))
789 return false;
790
791 break;
792 }
793
794 case Type::DependentAddressSpace: {
795 const auto *DepAddressSpace1 = cast<DependentAddressSpaceType>(T1);
796 const auto *DepAddressSpace2 = cast<DependentAddressSpaceType>(T2);
797 if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getAddrSpaceExpr(),
798 DepAddressSpace2->getAddrSpaceExpr()))
799 return false;
800 if (!IsStructurallyEquivalent(Context, DepAddressSpace1->getPointeeType(),
801 DepAddressSpace2->getPointeeType()))
802 return false;
803
804 break;
805 }
806
807 case Type::DependentSizedExtVector: {
808 const auto *Vec1 = cast<DependentSizedExtVectorType>(T1);
809 const auto *Vec2 = cast<DependentSizedExtVectorType>(T2);
810 if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
811 Vec2->getSizeExpr()))
812 return false;
813 if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
814 Vec2->getElementType()))
815 return false;
816 break;
817 }
818
819 case Type::DependentVector: {
820 const auto *Vec1 = cast<DependentVectorType>(T1);
821 const auto *Vec2 = cast<DependentVectorType>(T2);
822 if (Vec1->getVectorKind() != Vec2->getVectorKind())
823 return false;
824 if (!IsStructurallyEquivalent(Context, Vec1->getSizeExpr(),
825 Vec2->getSizeExpr()))
826 return false;
827 if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
828 Vec2->getElementType()))
829 return false;
830 break;
831 }
832
833 case Type::Vector:
834 case Type::ExtVector: {
835 const auto *Vec1 = cast<VectorType>(T1);
836 const auto *Vec2 = cast<VectorType>(T2);
837 if (!IsStructurallyEquivalent(Context, Vec1->getElementType(),
838 Vec2->getElementType()))
839 return false;
840 if (Vec1->getNumElements() != Vec2->getNumElements())
841 return false;
842 if (Vec1->getVectorKind() != Vec2->getVectorKind())
843 return false;
844 break;
845 }
846
847 case Type::DependentSizedMatrix: {
848 const DependentSizedMatrixType *Mat1 = cast<DependentSizedMatrixType>(T1);
849 const DependentSizedMatrixType *Mat2 = cast<DependentSizedMatrixType>(T2);
850 // The element types, row and column expressions must be structurally
851 // equivalent.
852 if (!IsStructurallyEquivalent(Context, Mat1->getRowExpr(),
853 Mat2->getRowExpr()) ||
854 !IsStructurallyEquivalent(Context, Mat1->getColumnExpr(),
855 Mat2->getColumnExpr()) ||
856 !IsStructurallyEquivalent(Context, Mat1->getElementType(),
857 Mat2->getElementType()))
858 return false;
859 break;
860 }
861
862 case Type::ConstantMatrix: {
863 const ConstantMatrixType *Mat1 = cast<ConstantMatrixType>(T1);
864 const ConstantMatrixType *Mat2 = cast<ConstantMatrixType>(T2);
865 // The element types must be structurally equivalent and the number of rows
866 // and columns must match.
867 if (!IsStructurallyEquivalent(Context, Mat1->getElementType(),
868 Mat2->getElementType()) ||
869 Mat1->getNumRows() != Mat2->getNumRows() ||
870 Mat1->getNumColumns() != Mat2->getNumColumns())
871 return false;
872 break;
873 }
874
875 case Type::FunctionProto: {
876 const auto *Proto1 = cast<FunctionProtoType>(T1);
877 const auto *Proto2 = cast<FunctionProtoType>(T2);
878
879 if (Proto1->getNumParams() != Proto2->getNumParams())
880 return false;
881 for (unsigned I = 0, N = Proto1->getNumParams(); I != N; ++I) {
882 if (!IsStructurallyEquivalent(Context, Proto1->getParamType(I),
883 Proto2->getParamType(I)))
884 return false;
885 }
886 if (Proto1->isVariadic() != Proto2->isVariadic())
887 return false;
888
889 if (Proto1->getMethodQuals() != Proto2->getMethodQuals())
890 return false;
891
892 // Check exceptions, this information is lost in canonical type.
893 const auto *OrigProto1 =
894 cast<FunctionProtoType>(OrigT1.getDesugaredType(Context.FromCtx));
895 const auto *OrigProto2 =
896 cast<FunctionProtoType>(OrigT2.getDesugaredType(Context.ToCtx));
897 if (!IsEquivalentExceptionSpec(Context, OrigProto1, OrigProto2))
898 return false;
899
900 // Fall through to check the bits common with FunctionNoProtoType.
901 LLVM_FALLTHROUGH;
902 }
903
904 case Type::FunctionNoProto: {
905 const auto *Function1 = cast<FunctionType>(T1);
906 const auto *Function2 = cast<FunctionType>(T2);
907 if (!IsStructurallyEquivalent(Context, Function1->getReturnType(),
908 Function2->getReturnType()))
909 return false;
910 if (!IsStructurallyEquivalent(Context, Function1->getExtInfo(),
911 Function2->getExtInfo()))
912 return false;
913 break;
914 }
915
916 case Type::UnresolvedUsing:
917 if (!IsStructurallyEquivalent(Context,
918 cast<UnresolvedUsingType>(T1)->getDecl(),
919 cast<UnresolvedUsingType>(T2)->getDecl()))
920 return false;
921 break;
922
923 case Type::Attributed:
924 if (!IsStructurallyEquivalent(Context,
925 cast<AttributedType>(T1)->getModifiedType(),
926 cast<AttributedType>(T2)->getModifiedType()))
927 return false;
928 if (!IsStructurallyEquivalent(
929 Context, cast<AttributedType>(T1)->getEquivalentType(),
930 cast<AttributedType>(T2)->getEquivalentType()))
931 return false;
932 break;
933
934 case Type::Paren:
935 if (!IsStructurallyEquivalent(Context, cast<ParenType>(T1)->getInnerType(),
936 cast<ParenType>(T2)->getInnerType()))
937 return false;
938 break;
939
940 case Type::MacroQualified:
941 if (!IsStructurallyEquivalent(
942 Context, cast<MacroQualifiedType>(T1)->getUnderlyingType(),
943 cast<MacroQualifiedType>(T2)->getUnderlyingType()))
944 return false;
945 break;
946
947 case Type::Typedef:
948 if (!IsStructurallyEquivalent(Context, cast<TypedefType>(T1)->getDecl(),
949 cast<TypedefType>(T2)->getDecl()))
950 return false;
951 break;
952
953 case Type::TypeOfExpr:
954 if (!IsStructurallyEquivalent(
955 Context, cast<TypeOfExprType>(T1)->getUnderlyingExpr(),
956 cast<TypeOfExprType>(T2)->getUnderlyingExpr()))
957 return false;
958 break;
959
960 case Type::TypeOf:
961 if (!IsStructurallyEquivalent(Context,
962 cast<TypeOfType>(T1)->getUnderlyingType(),
963 cast<TypeOfType>(T2)->getUnderlyingType()))
964 return false;
965 break;
966
967 case Type::UnaryTransform:
968 if (!IsStructurallyEquivalent(
969 Context, cast<UnaryTransformType>(T1)->getUnderlyingType(),
970 cast<UnaryTransformType>(T2)->getUnderlyingType()))
971 return false;
972 break;
973
974 case Type::Decltype:
975 if (!IsStructurallyEquivalent(Context,
976 cast<DecltypeType>(T1)->getUnderlyingExpr(),
977 cast<DecltypeType>(T2)->getUnderlyingExpr()))
978 return false;
979 break;
980
981 case Type::Auto: {
982 auto *Auto1 = cast<AutoType>(T1);
983 auto *Auto2 = cast<AutoType>(T2);
984 if (!IsStructurallyEquivalent(Context, Auto1->getDeducedType(),
985 Auto2->getDeducedType()))
986 return false;
987 if (Auto1->isConstrained() != Auto2->isConstrained())
988 return false;
989 if (Auto1->isConstrained()) {
990 if (Auto1->getTypeConstraintConcept() !=
991 Auto2->getTypeConstraintConcept())
992 return false;
993 ArrayRef<TemplateArgument> Auto1Args =
994 Auto1->getTypeConstraintArguments();
995 ArrayRef<TemplateArgument> Auto2Args =
996 Auto2->getTypeConstraintArguments();
997 if (Auto1Args.size() != Auto2Args.size())
998 return false;
999 for (unsigned I = 0, N = Auto1Args.size(); I != N; ++I) {
1000 if (!IsStructurallyEquivalent(Context, Auto1Args[I], Auto2Args[I]))
1001 return false;
1002 }
1003 }
1004 break;
1005 }
1006
1007 case Type::DeducedTemplateSpecialization: {
1008 const auto *DT1 = cast<DeducedTemplateSpecializationType>(T1);
1009 const auto *DT2 = cast<DeducedTemplateSpecializationType>(T2);
1010 if (!IsStructurallyEquivalent(Context, DT1->getTemplateName(),
1011 DT2->getTemplateName()))
1012 return false;
1013 if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(),
1014 DT2->getDeducedType()))
1015 return false;
1016 break;
1017 }
1018
1019 case Type::Record:
1020 case Type::Enum:
1021 if (!IsStructurallyEquivalent(Context, cast<TagType>(T1)->getDecl(),
1022 cast<TagType>(T2)->getDecl()))
1023 return false;
1024 break;
1025
1026 case Type::TemplateTypeParm: {
1027 const auto *Parm1 = cast<TemplateTypeParmType>(T1);
1028 const auto *Parm2 = cast<TemplateTypeParmType>(T2);
1029 if (Parm1->getDepth() != Parm2->getDepth())
1030 return false;
1031 if (Parm1->getIndex() != Parm2->getIndex())
1032 return false;
1033 if (Parm1->isParameterPack() != Parm2->isParameterPack())
1034 return false;
1035
1036 // Names of template type parameters are never significant.
1037 break;
1038 }
1039
1040 case Type::SubstTemplateTypeParm: {
1041 const auto *Subst1 = cast<SubstTemplateTypeParmType>(T1);
1042 const auto *Subst2 = cast<SubstTemplateTypeParmType>(T2);
1043 if (!IsStructurallyEquivalent(Context,
1044 QualType(Subst1->getReplacedParameter(), 0),
1045 QualType(Subst2->getReplacedParameter(), 0)))
1046 return false;
1047 if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(),
1048 Subst2->getReplacementType()))
1049 return false;
1050 break;
1051 }
1052
1053 case Type::SubstTemplateTypeParmPack: {
1054 const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(T1);
1055 const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(T2);
1056 if (!IsStructurallyEquivalent(Context,
1057 QualType(Subst1->getReplacedParameter(), 0),
1058 QualType(Subst2->getReplacedParameter(), 0)))
1059 return false;
1060 if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(),
1061 Subst2->getArgumentPack()))
1062 return false;
1063 break;
1064 }
1065
1066 case Type::TemplateSpecialization: {
1067 const auto *Spec1 = cast<TemplateSpecializationType>(T1);
1068 const auto *Spec2 = cast<TemplateSpecializationType>(T2);
1069 if (!IsStructurallyEquivalent(Context, Spec1->getTemplateName(),
1070 Spec2->getTemplateName()))
1071 return false;
1072 if (Spec1->getNumArgs() != Spec2->getNumArgs())
1073 return false;
1074 for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
1075 if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
1076 Spec2->getArg(I)))
1077 return false;
1078 }
1079 break;
1080 }
1081
1082 case Type::Elaborated: {
1083 const auto *Elab1 = cast<ElaboratedType>(T1);
1084 const auto *Elab2 = cast<ElaboratedType>(T2);
1085 // CHECKME: what if a keyword is ETK_None or ETK_typename ?
1086 if (Elab1->getKeyword() != Elab2->getKeyword())
1087 return false;
1088 if (!IsStructurallyEquivalent(Context, Elab1->getQualifier(),
1089 Elab2->getQualifier()))
1090 return false;
1091 if (!IsStructurallyEquivalent(Context, Elab1->getNamedType(),
1092 Elab2->getNamedType()))
1093 return false;
1094 break;
1095 }
1096
1097 case Type::InjectedClassName: {
1098 const auto *Inj1 = cast<InjectedClassNameType>(T1);
1099 const auto *Inj2 = cast<InjectedClassNameType>(T2);
1100 if (!IsStructurallyEquivalent(Context,
1101 Inj1->getInjectedSpecializationType(),
1102 Inj2->getInjectedSpecializationType()))
1103 return false;
1104 break;
1105 }
1106
1107 case Type::DependentName: {
1108 const auto *Typename1 = cast<DependentNameType>(T1);
1109 const auto *Typename2 = cast<DependentNameType>(T2);
1110 if (!IsStructurallyEquivalent(Context, Typename1->getQualifier(),
1111 Typename2->getQualifier()))
1112 return false;
1113 if (!IsStructurallyEquivalent(Typename1->getIdentifier(),
1114 Typename2->getIdentifier()))
1115 return false;
1116
1117 break;
1118 }
1119
1120 case Type::DependentTemplateSpecialization: {
1121 const auto *Spec1 = cast<DependentTemplateSpecializationType>(T1);
1122 const auto *Spec2 = cast<DependentTemplateSpecializationType>(T2);
1123 if (!IsStructurallyEquivalent(Context, Spec1->getQualifier(),
1124 Spec2->getQualifier()))
1125 return false;
1126 if (!IsStructurallyEquivalent(Spec1->getIdentifier(),
1127 Spec2->getIdentifier()))
1128 return false;
1129 if (Spec1->getNumArgs() != Spec2->getNumArgs())
1130 return false;
1131 for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) {
1132 if (!IsStructurallyEquivalent(Context, Spec1->getArg(I),
1133 Spec2->getArg(I)))
1134 return false;
1135 }
1136 break;
1137 }
1138
1139 case Type::PackExpansion:
1140 if (!IsStructurallyEquivalent(Context,
1141 cast<PackExpansionType>(T1)->getPattern(),
1142 cast<PackExpansionType>(T2)->getPattern()))
1143 return false;
1144 break;
1145
1146 case Type::ObjCInterface: {
1147 const auto *Iface1 = cast<ObjCInterfaceType>(T1);
1148 const auto *Iface2 = cast<ObjCInterfaceType>(T2);
1149 if (!IsStructurallyEquivalent(Context, Iface1->getDecl(),
1150 Iface2->getDecl()))
1151 return false;
1152 break;
1153 }
1154
1155 case Type::ObjCTypeParam: {
1156 const auto *Obj1 = cast<ObjCTypeParamType>(T1);
1157 const auto *Obj2 = cast<ObjCTypeParamType>(T2);
1158 if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl()))
1159 return false;
1160
1161 if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
1162 return false;
1163 for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
1164 if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
1165 Obj2->getProtocol(I)))
1166 return false;
1167 }
1168 break;
1169 }
1170
1171 case Type::ObjCObject: {
1172 const auto *Obj1 = cast<ObjCObjectType>(T1);
1173 const auto *Obj2 = cast<ObjCObjectType>(T2);
1174 if (!IsStructurallyEquivalent(Context, Obj1->getBaseType(),
1175 Obj2->getBaseType()))
1176 return false;
1177 if (Obj1->getNumProtocols() != Obj2->getNumProtocols())
1178 return false;
1179 for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) {
1180 if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I),
1181 Obj2->getProtocol(I)))
1182 return false;
1183 }
1184 break;
1185 }
1186
1187 case Type::ObjCObjectPointer: {
1188 const auto *Ptr1 = cast<ObjCObjectPointerType>(T1);
1189 const auto *Ptr2 = cast<ObjCObjectPointerType>(T2);
1190 if (!IsStructurallyEquivalent(Context, Ptr1->getPointeeType(),
1191 Ptr2->getPointeeType()))
1192 return false;
1193 break;
1194 }
1195
1196 case Type::Atomic:
1197 if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(),
1198 cast<AtomicType>(T2)->getValueType()))
1199 return false;
1200 break;
1201
1202 case Type::Pipe:
1203 if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(),
1204 cast<PipeType>(T2)->getElementType()))
1205 return false;
1206 break;
1207 case Type::ExtInt: {
1208 const auto *Int1 = cast<ExtIntType>(T1);
1209 const auto *Int2 = cast<ExtIntType>(T2);
1210
1211 if (Int1->isUnsigned() != Int2->isUnsigned() ||
1212 Int1->getNumBits() != Int2->getNumBits())
1213 return false;
1214 break;
1215 }
1216 case Type::DependentExtInt: {
1217 const auto *Int1 = cast<DependentExtIntType>(T1);
1218 const auto *Int2 = cast<DependentExtIntType>(T2);
1219
1220 if (Int1->isUnsigned() != Int2->isUnsigned() ||
1221 !IsStructurallyEquivalent(Context, Int1->getNumBitsExpr(),
1222 Int2->getNumBitsExpr()))
1223 return false;
1224 }
1225 } // end switch
1226
1227 return true;
1228 }
1229
1230 /// Determine structural equivalence of two fields.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,FieldDecl * Field1,FieldDecl * Field2)1231 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1232 FieldDecl *Field1, FieldDecl *Field2) {
1233 const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext());
1234
1235 // For anonymous structs/unions, match up the anonymous struct/union type
1236 // declarations directly, so that we don't go off searching for anonymous
1237 // types
1238 if (Field1->isAnonymousStructOrUnion() &&
1239 Field2->isAnonymousStructOrUnion()) {
1240 RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl();
1241 RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl();
1242 return IsStructurallyEquivalent(Context, D1, D2);
1243 }
1244
1245 // Check for equivalent field names.
1246 IdentifierInfo *Name1 = Field1->getIdentifier();
1247 IdentifierInfo *Name2 = Field2->getIdentifier();
1248 if (!::IsStructurallyEquivalent(Name1, Name2)) {
1249 if (Context.Complain) {
1250 Context.Diag2(
1251 Owner2->getLocation(),
1252 Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1253 << Context.ToCtx.getTypeDeclType(Owner2);
1254 Context.Diag2(Field2->getLocation(), diag::note_odr_field_name)
1255 << Field2->getDeclName();
1256 Context.Diag1(Field1->getLocation(), diag::note_odr_field_name)
1257 << Field1->getDeclName();
1258 }
1259 return false;
1260 }
1261
1262 if (!IsStructurallyEquivalent(Context, Field1->getType(),
1263 Field2->getType())) {
1264 if (Context.Complain) {
1265 Context.Diag2(
1266 Owner2->getLocation(),
1267 Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent))
1268 << Context.ToCtx.getTypeDeclType(Owner2);
1269 Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1270 << Field2->getDeclName() << Field2->getType();
1271 Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1272 << Field1->getDeclName() << Field1->getType();
1273 }
1274 return false;
1275 }
1276
1277 if (Field1->isBitField())
1278 return IsStructurallyEquivalent(Context, Field1->getBitWidth(),
1279 Field2->getBitWidth());
1280
1281 return true;
1282 }
1283
1284 /// Determine structural equivalence of two methods.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,CXXMethodDecl * Method1,CXXMethodDecl * Method2)1285 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1286 CXXMethodDecl *Method1,
1287 CXXMethodDecl *Method2) {
1288 bool PropertiesEqual =
1289 Method1->getDeclKind() == Method2->getDeclKind() &&
1290 Method1->getRefQualifier() == Method2->getRefQualifier() &&
1291 Method1->getAccess() == Method2->getAccess() &&
1292 Method1->getOverloadedOperator() == Method2->getOverloadedOperator() &&
1293 Method1->isStatic() == Method2->isStatic() &&
1294 Method1->isConst() == Method2->isConst() &&
1295 Method1->isVolatile() == Method2->isVolatile() &&
1296 Method1->isVirtual() == Method2->isVirtual() &&
1297 Method1->isPure() == Method2->isPure() &&
1298 Method1->isDefaulted() == Method2->isDefaulted() &&
1299 Method1->isDeleted() == Method2->isDeleted();
1300 if (!PropertiesEqual)
1301 return false;
1302 // FIXME: Check for 'final'.
1303
1304 if (auto *Constructor1 = dyn_cast<CXXConstructorDecl>(Method1)) {
1305 auto *Constructor2 = cast<CXXConstructorDecl>(Method2);
1306 if (!Constructor1->getExplicitSpecifier().isEquivalent(
1307 Constructor2->getExplicitSpecifier()))
1308 return false;
1309 }
1310
1311 if (auto *Conversion1 = dyn_cast<CXXConversionDecl>(Method1)) {
1312 auto *Conversion2 = cast<CXXConversionDecl>(Method2);
1313 if (!Conversion1->getExplicitSpecifier().isEquivalent(
1314 Conversion2->getExplicitSpecifier()))
1315 return false;
1316 if (!IsStructurallyEquivalent(Context, Conversion1->getConversionType(),
1317 Conversion2->getConversionType()))
1318 return false;
1319 }
1320
1321 const IdentifierInfo *Name1 = Method1->getIdentifier();
1322 const IdentifierInfo *Name2 = Method2->getIdentifier();
1323 if (!::IsStructurallyEquivalent(Name1, Name2)) {
1324 return false;
1325 // TODO: Names do not match, add warning like at check for FieldDecl.
1326 }
1327
1328 // Check the prototypes.
1329 if (!::IsStructurallyEquivalent(Context,
1330 Method1->getType(), Method2->getType()))
1331 return false;
1332
1333 return true;
1334 }
1335
1336 /// Determine structural equivalence of two lambda classes.
1337 static bool
IsStructurallyEquivalentLambdas(StructuralEquivalenceContext & Context,CXXRecordDecl * D1,CXXRecordDecl * D2)1338 IsStructurallyEquivalentLambdas(StructuralEquivalenceContext &Context,
1339 CXXRecordDecl *D1, CXXRecordDecl *D2) {
1340 assert(D1->isLambda() && D2->isLambda() &&
1341 "Must be called on lambda classes");
1342 if (!IsStructurallyEquivalent(Context, D1->getLambdaCallOperator(),
1343 D2->getLambdaCallOperator()))
1344 return false;
1345
1346 return true;
1347 }
1348
1349 /// Determine structural equivalence of two records.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,RecordDecl * D1,RecordDecl * D2)1350 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1351 RecordDecl *D1, RecordDecl *D2) {
1352
1353 // Check for equivalent structure names.
1354 IdentifierInfo *Name1 = D1->getIdentifier();
1355 if (!Name1 && D1->getTypedefNameForAnonDecl())
1356 Name1 = D1->getTypedefNameForAnonDecl()->getIdentifier();
1357 IdentifierInfo *Name2 = D2->getIdentifier();
1358 if (!Name2 && D2->getTypedefNameForAnonDecl())
1359 Name2 = D2->getTypedefNameForAnonDecl()->getIdentifier();
1360 if (!IsStructurallyEquivalent(Name1, Name2))
1361 return false;
1362
1363 if (D1->isUnion() != D2->isUnion()) {
1364 if (Context.Complain) {
1365 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1366 diag::err_odr_tag_type_inconsistent))
1367 << Context.ToCtx.getTypeDeclType(D2);
1368 Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here)
1369 << D1->getDeclName() << (unsigned)D1->getTagKind();
1370 }
1371 return false;
1372 }
1373
1374 if (!D1->getDeclName() && !D2->getDeclName()) {
1375 // If both anonymous structs/unions are in a record context, make sure
1376 // they occur in the same location in the context records.
1377 if (Optional<unsigned> Index1 =
1378 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(D1)) {
1379 if (Optional<unsigned> Index2 =
1380 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(
1381 D2)) {
1382 if (*Index1 != *Index2)
1383 return false;
1384 }
1385 }
1386 }
1387
1388 // If both declarations are class template specializations, we know
1389 // the ODR applies, so check the template and template arguments.
1390 const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(D1);
1391 const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(D2);
1392 if (Spec1 && Spec2) {
1393 // Check that the specialized templates are the same.
1394 if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(),
1395 Spec2->getSpecializedTemplate()))
1396 return false;
1397
1398 // Check that the template arguments are the same.
1399 if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size())
1400 return false;
1401
1402 for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I)
1403 if (!IsStructurallyEquivalent(Context, Spec1->getTemplateArgs().get(I),
1404 Spec2->getTemplateArgs().get(I)))
1405 return false;
1406 }
1407 // If one is a class template specialization and the other is not, these
1408 // structures are different.
1409 else if (Spec1 || Spec2)
1410 return false;
1411
1412 // Compare the definitions of these two records. If either or both are
1413 // incomplete (i.e. it is a forward decl), we assume that they are
1414 // equivalent.
1415 D1 = D1->getDefinition();
1416 D2 = D2->getDefinition();
1417 if (!D1 || !D2)
1418 return true;
1419
1420 // If any of the records has external storage and we do a minimal check (or
1421 // AST import) we assume they are equivalent. (If we didn't have this
1422 // assumption then `RecordDecl::LoadFieldsFromExternalStorage` could trigger
1423 // another AST import which in turn would call the structural equivalency
1424 // check again and finally we'd have an improper result.)
1425 if (Context.EqKind == StructuralEquivalenceKind::Minimal)
1426 if (D1->hasExternalLexicalStorage() || D2->hasExternalLexicalStorage())
1427 return true;
1428
1429 // If one definition is currently being defined, we do not compare for
1430 // equality and we assume that the decls are equal.
1431 if (D1->isBeingDefined() || D2->isBeingDefined())
1432 return true;
1433
1434 if (auto *D1CXX = dyn_cast<CXXRecordDecl>(D1)) {
1435 if (auto *D2CXX = dyn_cast<CXXRecordDecl>(D2)) {
1436 if (D1CXX->hasExternalLexicalStorage() &&
1437 !D1CXX->isCompleteDefinition()) {
1438 D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX);
1439 }
1440
1441 if (D1CXX->isLambda() != D2CXX->isLambda())
1442 return false;
1443 if (D1CXX->isLambda()) {
1444 if (!IsStructurallyEquivalentLambdas(Context, D1CXX, D2CXX))
1445 return false;
1446 }
1447
1448 if (D1CXX->getNumBases() != D2CXX->getNumBases()) {
1449 if (Context.Complain) {
1450 Context.Diag2(D2->getLocation(),
1451 Context.getApplicableDiagnostic(
1452 diag::err_odr_tag_type_inconsistent))
1453 << Context.ToCtx.getTypeDeclType(D2);
1454 Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases)
1455 << D2CXX->getNumBases();
1456 Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases)
1457 << D1CXX->getNumBases();
1458 }
1459 return false;
1460 }
1461
1462 // Check the base classes.
1463 for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(),
1464 BaseEnd1 = D1CXX->bases_end(),
1465 Base2 = D2CXX->bases_begin();
1466 Base1 != BaseEnd1; ++Base1, ++Base2) {
1467 if (!IsStructurallyEquivalent(Context, Base1->getType(),
1468 Base2->getType())) {
1469 if (Context.Complain) {
1470 Context.Diag2(D2->getLocation(),
1471 Context.getApplicableDiagnostic(
1472 diag::err_odr_tag_type_inconsistent))
1473 << Context.ToCtx.getTypeDeclType(D2);
1474 Context.Diag2(Base2->getBeginLoc(), diag::note_odr_base)
1475 << Base2->getType() << Base2->getSourceRange();
1476 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1477 << Base1->getType() << Base1->getSourceRange();
1478 }
1479 return false;
1480 }
1481
1482 // Check virtual vs. non-virtual inheritance mismatch.
1483 if (Base1->isVirtual() != Base2->isVirtual()) {
1484 if (Context.Complain) {
1485 Context.Diag2(D2->getLocation(),
1486 Context.getApplicableDiagnostic(
1487 diag::err_odr_tag_type_inconsistent))
1488 << Context.ToCtx.getTypeDeclType(D2);
1489 Context.Diag2(Base2->getBeginLoc(), diag::note_odr_virtual_base)
1490 << Base2->isVirtual() << Base2->getSourceRange();
1491 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1492 << Base1->isVirtual() << Base1->getSourceRange();
1493 }
1494 return false;
1495 }
1496 }
1497
1498 // Check the friends for consistency.
1499 CXXRecordDecl::friend_iterator Friend2 = D2CXX->friend_begin(),
1500 Friend2End = D2CXX->friend_end();
1501 for (CXXRecordDecl::friend_iterator Friend1 = D1CXX->friend_begin(),
1502 Friend1End = D1CXX->friend_end();
1503 Friend1 != Friend1End; ++Friend1, ++Friend2) {
1504 if (Friend2 == Friend2End) {
1505 if (Context.Complain) {
1506 Context.Diag2(D2->getLocation(),
1507 Context.getApplicableDiagnostic(
1508 diag::err_odr_tag_type_inconsistent))
1509 << Context.ToCtx.getTypeDeclType(D2CXX);
1510 Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1511 Context.Diag2(D2->getLocation(), diag::note_odr_missing_friend);
1512 }
1513 return false;
1514 }
1515
1516 if (!IsStructurallyEquivalent(Context, *Friend1, *Friend2)) {
1517 if (Context.Complain) {
1518 Context.Diag2(D2->getLocation(),
1519 Context.getApplicableDiagnostic(
1520 diag::err_odr_tag_type_inconsistent))
1521 << Context.ToCtx.getTypeDeclType(D2CXX);
1522 Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend);
1523 Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1524 }
1525 return false;
1526 }
1527 }
1528
1529 if (Friend2 != Friend2End) {
1530 if (Context.Complain) {
1531 Context.Diag2(D2->getLocation(),
1532 Context.getApplicableDiagnostic(
1533 diag::err_odr_tag_type_inconsistent))
1534 << Context.ToCtx.getTypeDeclType(D2);
1535 Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend);
1536 Context.Diag1(D1->getLocation(), diag::note_odr_missing_friend);
1537 }
1538 return false;
1539 }
1540 } else if (D1CXX->getNumBases() > 0) {
1541 if (Context.Complain) {
1542 Context.Diag2(D2->getLocation(),
1543 Context.getApplicableDiagnostic(
1544 diag::err_odr_tag_type_inconsistent))
1545 << Context.ToCtx.getTypeDeclType(D2);
1546 const CXXBaseSpecifier *Base1 = D1CXX->bases_begin();
1547 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base)
1548 << Base1->getType() << Base1->getSourceRange();
1549 Context.Diag2(D2->getLocation(), diag::note_odr_missing_base);
1550 }
1551 return false;
1552 }
1553 }
1554
1555 // Check the fields for consistency.
1556 RecordDecl::field_iterator Field2 = D2->field_begin(),
1557 Field2End = D2->field_end();
1558 for (RecordDecl::field_iterator Field1 = D1->field_begin(),
1559 Field1End = D1->field_end();
1560 Field1 != Field1End; ++Field1, ++Field2) {
1561 if (Field2 == Field2End) {
1562 if (Context.Complain) {
1563 Context.Diag2(D2->getLocation(),
1564 Context.getApplicableDiagnostic(
1565 diag::err_odr_tag_type_inconsistent))
1566 << Context.ToCtx.getTypeDeclType(D2);
1567 Context.Diag1(Field1->getLocation(), diag::note_odr_field)
1568 << Field1->getDeclName() << Field1->getType();
1569 Context.Diag2(D2->getLocation(), diag::note_odr_missing_field);
1570 }
1571 return false;
1572 }
1573
1574 if (!IsStructurallyEquivalent(Context, *Field1, *Field2))
1575 return false;
1576 }
1577
1578 if (Field2 != Field2End) {
1579 if (Context.Complain) {
1580 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1581 diag::err_odr_tag_type_inconsistent))
1582 << Context.ToCtx.getTypeDeclType(D2);
1583 Context.Diag2(Field2->getLocation(), diag::note_odr_field)
1584 << Field2->getDeclName() << Field2->getType();
1585 Context.Diag1(D1->getLocation(), diag::note_odr_missing_field);
1586 }
1587 return false;
1588 }
1589
1590 return true;
1591 }
1592
1593 /// Determine structural equivalence of two enums.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,EnumDecl * D1,EnumDecl * D2)1594 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1595 EnumDecl *D1, EnumDecl *D2) {
1596
1597 // Check for equivalent enum names.
1598 IdentifierInfo *Name1 = D1->getIdentifier();
1599 if (!Name1 && D1->getTypedefNameForAnonDecl())
1600 Name1 = D1->getTypedefNameForAnonDecl()->getIdentifier();
1601 IdentifierInfo *Name2 = D2->getIdentifier();
1602 if (!Name2 && D2->getTypedefNameForAnonDecl())
1603 Name2 = D2->getTypedefNameForAnonDecl()->getIdentifier();
1604 if (!IsStructurallyEquivalent(Name1, Name2))
1605 return false;
1606
1607 // Compare the definitions of these two enums. If either or both are
1608 // incomplete (i.e. forward declared), we assume that they are equivalent.
1609 D1 = D1->getDefinition();
1610 D2 = D2->getDefinition();
1611 if (!D1 || !D2)
1612 return true;
1613
1614 EnumDecl::enumerator_iterator EC2 = D2->enumerator_begin(),
1615 EC2End = D2->enumerator_end();
1616 for (EnumDecl::enumerator_iterator EC1 = D1->enumerator_begin(),
1617 EC1End = D1->enumerator_end();
1618 EC1 != EC1End; ++EC1, ++EC2) {
1619 if (EC2 == EC2End) {
1620 if (Context.Complain) {
1621 Context.Diag2(D2->getLocation(),
1622 Context.getApplicableDiagnostic(
1623 diag::err_odr_tag_type_inconsistent))
1624 << Context.ToCtx.getTypeDeclType(D2);
1625 Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1626 << EC1->getDeclName() << EC1->getInitVal().toString(10);
1627 Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator);
1628 }
1629 return false;
1630 }
1631
1632 llvm::APSInt Val1 = EC1->getInitVal();
1633 llvm::APSInt Val2 = EC2->getInitVal();
1634 if (!llvm::APSInt::isSameValue(Val1, Val2) ||
1635 !IsStructurallyEquivalent(EC1->getIdentifier(), EC2->getIdentifier())) {
1636 if (Context.Complain) {
1637 Context.Diag2(D2->getLocation(),
1638 Context.getApplicableDiagnostic(
1639 diag::err_odr_tag_type_inconsistent))
1640 << Context.ToCtx.getTypeDeclType(D2);
1641 Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1642 << EC2->getDeclName() << EC2->getInitVal().toString(10);
1643 Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator)
1644 << EC1->getDeclName() << EC1->getInitVal().toString(10);
1645 }
1646 return false;
1647 }
1648 }
1649
1650 if (EC2 != EC2End) {
1651 if (Context.Complain) {
1652 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic(
1653 diag::err_odr_tag_type_inconsistent))
1654 << Context.ToCtx.getTypeDeclType(D2);
1655 Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator)
1656 << EC2->getDeclName() << EC2->getInitVal().toString(10);
1657 Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator);
1658 }
1659 return false;
1660 }
1661
1662 return true;
1663 }
1664
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,TemplateParameterList * Params1,TemplateParameterList * Params2)1665 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1666 TemplateParameterList *Params1,
1667 TemplateParameterList *Params2) {
1668 if (Params1->size() != Params2->size()) {
1669 if (Context.Complain) {
1670 Context.Diag2(Params2->getTemplateLoc(),
1671 Context.getApplicableDiagnostic(
1672 diag::err_odr_different_num_template_parameters))
1673 << Params1->size() << Params2->size();
1674 Context.Diag1(Params1->getTemplateLoc(),
1675 diag::note_odr_template_parameter_list);
1676 }
1677 return false;
1678 }
1679
1680 for (unsigned I = 0, N = Params1->size(); I != N; ++I) {
1681 if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) {
1682 if (Context.Complain) {
1683 Context.Diag2(Params2->getParam(I)->getLocation(),
1684 Context.getApplicableDiagnostic(
1685 diag::err_odr_different_template_parameter_kind));
1686 Context.Diag1(Params1->getParam(I)->getLocation(),
1687 diag::note_odr_template_parameter_here);
1688 }
1689 return false;
1690 }
1691
1692 if (!IsStructurallyEquivalent(Context, Params1->getParam(I),
1693 Params2->getParam(I)))
1694 return false;
1695 }
1696
1697 return true;
1698 }
1699
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,TemplateTypeParmDecl * D1,TemplateTypeParmDecl * D2)1700 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1701 TemplateTypeParmDecl *D1,
1702 TemplateTypeParmDecl *D2) {
1703 if (D1->isParameterPack() != D2->isParameterPack()) {
1704 if (Context.Complain) {
1705 Context.Diag2(D2->getLocation(),
1706 Context.getApplicableDiagnostic(
1707 diag::err_odr_parameter_pack_non_pack))
1708 << D2->isParameterPack();
1709 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1710 << D1->isParameterPack();
1711 }
1712 return false;
1713 }
1714
1715 return true;
1716 }
1717
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,NonTypeTemplateParmDecl * D1,NonTypeTemplateParmDecl * D2)1718 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1719 NonTypeTemplateParmDecl *D1,
1720 NonTypeTemplateParmDecl *D2) {
1721 if (D1->isParameterPack() != D2->isParameterPack()) {
1722 if (Context.Complain) {
1723 Context.Diag2(D2->getLocation(),
1724 Context.getApplicableDiagnostic(
1725 diag::err_odr_parameter_pack_non_pack))
1726 << D2->isParameterPack();
1727 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1728 << D1->isParameterPack();
1729 }
1730 return false;
1731 }
1732
1733 // Check types.
1734 if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) {
1735 if (Context.Complain) {
1736 Context.Diag2(D2->getLocation(),
1737 Context.getApplicableDiagnostic(
1738 diag::err_odr_non_type_parameter_type_inconsistent))
1739 << D2->getType() << D1->getType();
1740 Context.Diag1(D1->getLocation(), diag::note_odr_value_here)
1741 << D1->getType();
1742 }
1743 return false;
1744 }
1745
1746 return true;
1747 }
1748
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,TemplateTemplateParmDecl * D1,TemplateTemplateParmDecl * D2)1749 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1750 TemplateTemplateParmDecl *D1,
1751 TemplateTemplateParmDecl *D2) {
1752 if (D1->isParameterPack() != D2->isParameterPack()) {
1753 if (Context.Complain) {
1754 Context.Diag2(D2->getLocation(),
1755 Context.getApplicableDiagnostic(
1756 diag::err_odr_parameter_pack_non_pack))
1757 << D2->isParameterPack();
1758 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack)
1759 << D1->isParameterPack();
1760 }
1761 return false;
1762 }
1763
1764 // Check template parameter lists.
1765 return IsStructurallyEquivalent(Context, D1->getTemplateParameters(),
1766 D2->getTemplateParameters());
1767 }
1768
IsTemplateDeclCommonStructurallyEquivalent(StructuralEquivalenceContext & Ctx,TemplateDecl * D1,TemplateDecl * D2)1769 static bool IsTemplateDeclCommonStructurallyEquivalent(
1770 StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) {
1771 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1772 return false;
1773 if (!D1->getIdentifier()) // Special name
1774 if (D1->getNameAsString() != D2->getNameAsString())
1775 return false;
1776 return IsStructurallyEquivalent(Ctx, D1->getTemplateParameters(),
1777 D2->getTemplateParameters());
1778 }
1779
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,ClassTemplateDecl * D1,ClassTemplateDecl * D2)1780 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1781 ClassTemplateDecl *D1,
1782 ClassTemplateDecl *D2) {
1783 // Check template parameters.
1784 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1785 return false;
1786
1787 // Check the templated declaration.
1788 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(),
1789 D2->getTemplatedDecl());
1790 }
1791
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,FunctionTemplateDecl * D1,FunctionTemplateDecl * D2)1792 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1793 FunctionTemplateDecl *D1,
1794 FunctionTemplateDecl *D2) {
1795 // Check template parameters.
1796 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1797 return false;
1798
1799 // Check the templated declaration.
1800 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(),
1801 D2->getTemplatedDecl()->getType());
1802 }
1803
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,ConceptDecl * D1,ConceptDecl * D2)1804 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1805 ConceptDecl *D1,
1806 ConceptDecl *D2) {
1807 // Check template parameters.
1808 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2))
1809 return false;
1810
1811 // Check the constraint expression.
1812 return IsStructurallyEquivalent(Context, D1->getConstraintExpr(),
1813 D2->getConstraintExpr());
1814 }
1815
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,FriendDecl * D1,FriendDecl * D2)1816 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1817 FriendDecl *D1, FriendDecl *D2) {
1818 if ((D1->getFriendType() && D2->getFriendDecl()) ||
1819 (D1->getFriendDecl() && D2->getFriendType())) {
1820 return false;
1821 }
1822 if (D1->getFriendType() && D2->getFriendType())
1823 return IsStructurallyEquivalent(Context,
1824 D1->getFriendType()->getType(),
1825 D2->getFriendType()->getType());
1826 if (D1->getFriendDecl() && D2->getFriendDecl())
1827 return IsStructurallyEquivalent(Context, D1->getFriendDecl(),
1828 D2->getFriendDecl());
1829 return false;
1830 }
1831
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,TypedefNameDecl * D1,TypedefNameDecl * D2)1832 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1833 TypedefNameDecl *D1, TypedefNameDecl *D2) {
1834 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1835 return false;
1836
1837 return IsStructurallyEquivalent(Context, D1->getUnderlyingType(),
1838 D2->getUnderlyingType());
1839 }
1840
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,FunctionDecl * D1,FunctionDecl * D2)1841 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1842 FunctionDecl *D1, FunctionDecl *D2) {
1843 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier()))
1844 return false;
1845
1846 if (D1->isOverloadedOperator()) {
1847 if (!D2->isOverloadedOperator())
1848 return false;
1849 if (D1->getOverloadedOperator() != D2->getOverloadedOperator())
1850 return false;
1851 }
1852
1853 // FIXME: Consider checking for function attributes as well.
1854 if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType()))
1855 return false;
1856
1857 return true;
1858 }
1859
1860 /// Determine structural equivalence of two declarations.
IsStructurallyEquivalent(StructuralEquivalenceContext & Context,Decl * D1,Decl * D2)1861 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context,
1862 Decl *D1, Decl *D2) {
1863 // FIXME: Check for known structural equivalences via a callback of some sort.
1864
1865 D1 = D1->getCanonicalDecl();
1866 D2 = D2->getCanonicalDecl();
1867 std::pair<Decl *, Decl *> P{D1, D2};
1868
1869 // Check whether we already know that these two declarations are not
1870 // structurally equivalent.
1871 if (Context.NonEquivalentDecls.count(P))
1872 return false;
1873
1874 // Check if a check for these declarations is already pending.
1875 // If yes D1 and D2 will be checked later (from DeclsToCheck),
1876 // or these are already checked (and equivalent).
1877 bool Inserted = Context.VisitedDecls.insert(P).second;
1878 if (!Inserted)
1879 return true;
1880
1881 Context.DeclsToCheck.push(P);
1882
1883 return true;
1884 }
1885
Diag1(SourceLocation Loc,unsigned DiagID)1886 DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc,
1887 unsigned DiagID) {
1888 assert(Complain && "Not allowed to complain");
1889 if (LastDiagFromC2)
1890 FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics());
1891 LastDiagFromC2 = false;
1892 return FromCtx.getDiagnostics().Report(Loc, DiagID);
1893 }
1894
Diag2(SourceLocation Loc,unsigned DiagID)1895 DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc,
1896 unsigned DiagID) {
1897 assert(Complain && "Not allowed to complain");
1898 if (!LastDiagFromC2)
1899 ToCtx.getDiagnostics().notePriorDiagnosticFrom(FromCtx.getDiagnostics());
1900 LastDiagFromC2 = true;
1901 return ToCtx.getDiagnostics().Report(Loc, DiagID);
1902 }
1903
1904 Optional<unsigned>
findUntaggedStructOrUnionIndex(RecordDecl * Anon)1905 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) {
1906 ASTContext &Context = Anon->getASTContext();
1907 QualType AnonTy = Context.getRecordType(Anon);
1908
1909 const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext());
1910 if (!Owner)
1911 return None;
1912
1913 unsigned Index = 0;
1914 for (const auto *D : Owner->noload_decls()) {
1915 const auto *F = dyn_cast<FieldDecl>(D);
1916 if (!F)
1917 continue;
1918
1919 if (F->isAnonymousStructOrUnion()) {
1920 if (Context.hasSameType(F->getType(), AnonTy))
1921 break;
1922 ++Index;
1923 continue;
1924 }
1925
1926 // If the field looks like this:
1927 // struct { ... } A;
1928 QualType FieldType = F->getType();
1929 // In case of nested structs.
1930 while (const auto *ElabType = dyn_cast<ElaboratedType>(FieldType))
1931 FieldType = ElabType->getNamedType();
1932
1933 if (const auto *RecType = dyn_cast<RecordType>(FieldType)) {
1934 const RecordDecl *RecDecl = RecType->getDecl();
1935 if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) {
1936 if (Context.hasSameType(FieldType, AnonTy))
1937 break;
1938 ++Index;
1939 continue;
1940 }
1941 }
1942 }
1943
1944 return Index;
1945 }
1946
getApplicableDiagnostic(unsigned ErrorDiagnostic)1947 unsigned StructuralEquivalenceContext::getApplicableDiagnostic(
1948 unsigned ErrorDiagnostic) {
1949 if (ErrorOnTagTypeMismatch)
1950 return ErrorDiagnostic;
1951
1952 switch (ErrorDiagnostic) {
1953 case diag::err_odr_variable_type_inconsistent:
1954 return diag::warn_odr_variable_type_inconsistent;
1955 case diag::err_odr_variable_multiple_def:
1956 return diag::warn_odr_variable_multiple_def;
1957 case diag::err_odr_function_type_inconsistent:
1958 return diag::warn_odr_function_type_inconsistent;
1959 case diag::err_odr_tag_type_inconsistent:
1960 return diag::warn_odr_tag_type_inconsistent;
1961 case diag::err_odr_field_type_inconsistent:
1962 return diag::warn_odr_field_type_inconsistent;
1963 case diag::err_odr_ivar_type_inconsistent:
1964 return diag::warn_odr_ivar_type_inconsistent;
1965 case diag::err_odr_objc_superclass_inconsistent:
1966 return diag::warn_odr_objc_superclass_inconsistent;
1967 case diag::err_odr_objc_method_result_type_inconsistent:
1968 return diag::warn_odr_objc_method_result_type_inconsistent;
1969 case diag::err_odr_objc_method_num_params_inconsistent:
1970 return diag::warn_odr_objc_method_num_params_inconsistent;
1971 case diag::err_odr_objc_method_param_type_inconsistent:
1972 return diag::warn_odr_objc_method_param_type_inconsistent;
1973 case diag::err_odr_objc_method_variadic_inconsistent:
1974 return diag::warn_odr_objc_method_variadic_inconsistent;
1975 case diag::err_odr_objc_property_type_inconsistent:
1976 return diag::warn_odr_objc_property_type_inconsistent;
1977 case diag::err_odr_objc_property_impl_kind_inconsistent:
1978 return diag::warn_odr_objc_property_impl_kind_inconsistent;
1979 case diag::err_odr_objc_synthesize_ivar_inconsistent:
1980 return diag::warn_odr_objc_synthesize_ivar_inconsistent;
1981 case diag::err_odr_different_num_template_parameters:
1982 return diag::warn_odr_different_num_template_parameters;
1983 case diag::err_odr_different_template_parameter_kind:
1984 return diag::warn_odr_different_template_parameter_kind;
1985 case diag::err_odr_parameter_pack_non_pack:
1986 return diag::warn_odr_parameter_pack_non_pack;
1987 case diag::err_odr_non_type_parameter_type_inconsistent:
1988 return diag::warn_odr_non_type_parameter_type_inconsistent;
1989 }
1990 llvm_unreachable("Diagnostic kind not handled in preceding switch");
1991 }
1992
IsEquivalent(Decl * D1,Decl * D2)1993 bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) {
1994
1995 // Ensure that the implementation functions (all static functions in this TU)
1996 // never call the public ASTStructuralEquivalence::IsEquivalent() functions,
1997 // because that will wreak havoc the internal state (DeclsToCheck and
1998 // VisitedDecls members) and can cause faulty behaviour.
1999 // In other words: Do not start a graph search from a new node with the
2000 // internal data of another search in progress.
2001 // FIXME: Better encapsulation and separation of internal and public
2002 // functionality.
2003 assert(DeclsToCheck.empty());
2004 assert(VisitedDecls.empty());
2005
2006 if (!::IsStructurallyEquivalent(*this, D1, D2))
2007 return false;
2008
2009 return !Finish();
2010 }
2011
IsEquivalent(QualType T1,QualType T2)2012 bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) {
2013 assert(DeclsToCheck.empty());
2014 assert(VisitedDecls.empty());
2015 if (!::IsStructurallyEquivalent(*this, T1, T2))
2016 return false;
2017
2018 return !Finish();
2019 }
2020
IsEquivalent(Stmt * S1,Stmt * S2)2021 bool StructuralEquivalenceContext::IsEquivalent(Stmt *S1, Stmt *S2) {
2022 assert(DeclsToCheck.empty());
2023 assert(VisitedDecls.empty());
2024 if (!::IsStructurallyEquivalent(*this, S1, S2))
2025 return false;
2026
2027 return !Finish();
2028 }
2029
CheckCommonEquivalence(Decl * D1,Decl * D2)2030 bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) {
2031 // Check for equivalent described template.
2032 TemplateDecl *Template1 = D1->getDescribedTemplate();
2033 TemplateDecl *Template2 = D2->getDescribedTemplate();
2034 if ((Template1 != nullptr) != (Template2 != nullptr))
2035 return false;
2036 if (Template1 && !IsStructurallyEquivalent(*this, Template1, Template2))
2037 return false;
2038
2039 // FIXME: Move check for identifier names into this function.
2040
2041 return true;
2042 }
2043
CheckKindSpecificEquivalence(Decl * D1,Decl * D2)2044 bool StructuralEquivalenceContext::CheckKindSpecificEquivalence(
2045 Decl *D1, Decl *D2) {
2046
2047 // Kind mismatch.
2048 if (D1->getKind() != D2->getKind())
2049 return false;
2050
2051 // Cast the Decls to their actual subclass so that the right overload of
2052 // IsStructurallyEquivalent is called.
2053 switch (D1->getKind()) {
2054 #define ABSTRACT_DECL(DECL)
2055 #define DECL(DERIVED, BASE) \
2056 case Decl::Kind::DERIVED: \
2057 return ::IsStructurallyEquivalent(*this, static_cast<DERIVED##Decl *>(D1), \
2058 static_cast<DERIVED##Decl *>(D2));
2059 #include "clang/AST/DeclNodes.inc"
2060 }
2061 return true;
2062 }
2063
Finish()2064 bool StructuralEquivalenceContext::Finish() {
2065 while (!DeclsToCheck.empty()) {
2066 // Check the next declaration.
2067 std::pair<Decl *, Decl *> P = DeclsToCheck.front();
2068 DeclsToCheck.pop();
2069
2070 Decl *D1 = P.first;
2071 Decl *D2 = P.second;
2072
2073 bool Equivalent =
2074 CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2);
2075
2076 if (!Equivalent) {
2077 // Note that these two declarations are not equivalent (and we already
2078 // know about it).
2079 NonEquivalentDecls.insert(P);
2080
2081 return true;
2082 }
2083 }
2084
2085 return false;
2086 }
2087