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