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::Typedef: 949 if (!IsStructurallyEquivalent(Context, cast<TypedefType>(T1)->getDecl(), 950 cast<TypedefType>(T2)->getDecl())) 951 return false; 952 break; 953 954 case Type::TypeOfExpr: 955 if (!IsStructurallyEquivalent( 956 Context, cast<TypeOfExprType>(T1)->getUnderlyingExpr(), 957 cast<TypeOfExprType>(T2)->getUnderlyingExpr())) 958 return false; 959 break; 960 961 case Type::TypeOf: 962 if (!IsStructurallyEquivalent(Context, 963 cast<TypeOfType>(T1)->getUnderlyingType(), 964 cast<TypeOfType>(T2)->getUnderlyingType())) 965 return false; 966 break; 967 968 case Type::UnaryTransform: 969 if (!IsStructurallyEquivalent( 970 Context, cast<UnaryTransformType>(T1)->getUnderlyingType(), 971 cast<UnaryTransformType>(T2)->getUnderlyingType())) 972 return false; 973 break; 974 975 case Type::Decltype: 976 if (!IsStructurallyEquivalent(Context, 977 cast<DecltypeType>(T1)->getUnderlyingExpr(), 978 cast<DecltypeType>(T2)->getUnderlyingExpr())) 979 return false; 980 break; 981 982 case Type::Auto: { 983 auto *Auto1 = cast<AutoType>(T1); 984 auto *Auto2 = cast<AutoType>(T2); 985 if (!IsStructurallyEquivalent(Context, Auto1->getDeducedType(), 986 Auto2->getDeducedType())) 987 return false; 988 if (Auto1->isConstrained() != Auto2->isConstrained()) 989 return false; 990 if (Auto1->isConstrained()) { 991 if (Auto1->getTypeConstraintConcept() != 992 Auto2->getTypeConstraintConcept()) 993 return false; 994 ArrayRef<TemplateArgument> Auto1Args = 995 Auto1->getTypeConstraintArguments(); 996 ArrayRef<TemplateArgument> Auto2Args = 997 Auto2->getTypeConstraintArguments(); 998 if (Auto1Args.size() != Auto2Args.size()) 999 return false; 1000 for (unsigned I = 0, N = Auto1Args.size(); I != N; ++I) { 1001 if (!IsStructurallyEquivalent(Context, Auto1Args[I], Auto2Args[I])) 1002 return false; 1003 } 1004 } 1005 break; 1006 } 1007 1008 case Type::DeducedTemplateSpecialization: { 1009 const auto *DT1 = cast<DeducedTemplateSpecializationType>(T1); 1010 const auto *DT2 = cast<DeducedTemplateSpecializationType>(T2); 1011 if (!IsStructurallyEquivalent(Context, DT1->getTemplateName(), 1012 DT2->getTemplateName())) 1013 return false; 1014 if (!IsStructurallyEquivalent(Context, DT1->getDeducedType(), 1015 DT2->getDeducedType())) 1016 return false; 1017 break; 1018 } 1019 1020 case Type::Record: 1021 case Type::Enum: 1022 if (!IsStructurallyEquivalent(Context, cast<TagType>(T1)->getDecl(), 1023 cast<TagType>(T2)->getDecl())) 1024 return false; 1025 break; 1026 1027 case Type::TemplateTypeParm: { 1028 const auto *Parm1 = cast<TemplateTypeParmType>(T1); 1029 const auto *Parm2 = cast<TemplateTypeParmType>(T2); 1030 if (Parm1->getDepth() != Parm2->getDepth()) 1031 return false; 1032 if (Parm1->getIndex() != Parm2->getIndex()) 1033 return false; 1034 if (Parm1->isParameterPack() != Parm2->isParameterPack()) 1035 return false; 1036 1037 // Names of template type parameters are never significant. 1038 break; 1039 } 1040 1041 case Type::SubstTemplateTypeParm: { 1042 const auto *Subst1 = cast<SubstTemplateTypeParmType>(T1); 1043 const auto *Subst2 = cast<SubstTemplateTypeParmType>(T2); 1044 if (!IsStructurallyEquivalent(Context, 1045 QualType(Subst1->getReplacedParameter(), 0), 1046 QualType(Subst2->getReplacedParameter(), 0))) 1047 return false; 1048 if (!IsStructurallyEquivalent(Context, Subst1->getReplacementType(), 1049 Subst2->getReplacementType())) 1050 return false; 1051 break; 1052 } 1053 1054 case Type::SubstTemplateTypeParmPack: { 1055 const auto *Subst1 = cast<SubstTemplateTypeParmPackType>(T1); 1056 const auto *Subst2 = cast<SubstTemplateTypeParmPackType>(T2); 1057 if (!IsStructurallyEquivalent(Context, 1058 QualType(Subst1->getReplacedParameter(), 0), 1059 QualType(Subst2->getReplacedParameter(), 0))) 1060 return false; 1061 if (!IsStructurallyEquivalent(Context, Subst1->getArgumentPack(), 1062 Subst2->getArgumentPack())) 1063 return false; 1064 break; 1065 } 1066 1067 case Type::TemplateSpecialization: { 1068 const auto *Spec1 = cast<TemplateSpecializationType>(T1); 1069 const auto *Spec2 = cast<TemplateSpecializationType>(T2); 1070 if (!IsStructurallyEquivalent(Context, Spec1->getTemplateName(), 1071 Spec2->getTemplateName())) 1072 return false; 1073 if (Spec1->getNumArgs() != Spec2->getNumArgs()) 1074 return false; 1075 for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) { 1076 if (!IsStructurallyEquivalent(Context, Spec1->getArg(I), 1077 Spec2->getArg(I))) 1078 return false; 1079 } 1080 break; 1081 } 1082 1083 case Type::Elaborated: { 1084 const auto *Elab1 = cast<ElaboratedType>(T1); 1085 const auto *Elab2 = cast<ElaboratedType>(T2); 1086 // CHECKME: what if a keyword is ETK_None or ETK_typename ? 1087 if (Elab1->getKeyword() != Elab2->getKeyword()) 1088 return false; 1089 if (!IsStructurallyEquivalent(Context, Elab1->getQualifier(), 1090 Elab2->getQualifier())) 1091 return false; 1092 if (!IsStructurallyEquivalent(Context, Elab1->getNamedType(), 1093 Elab2->getNamedType())) 1094 return false; 1095 break; 1096 } 1097 1098 case Type::InjectedClassName: { 1099 const auto *Inj1 = cast<InjectedClassNameType>(T1); 1100 const auto *Inj2 = cast<InjectedClassNameType>(T2); 1101 if (!IsStructurallyEquivalent(Context, 1102 Inj1->getInjectedSpecializationType(), 1103 Inj2->getInjectedSpecializationType())) 1104 return false; 1105 break; 1106 } 1107 1108 case Type::DependentName: { 1109 const auto *Typename1 = cast<DependentNameType>(T1); 1110 const auto *Typename2 = cast<DependentNameType>(T2); 1111 if (!IsStructurallyEquivalent(Context, Typename1->getQualifier(), 1112 Typename2->getQualifier())) 1113 return false; 1114 if (!IsStructurallyEquivalent(Typename1->getIdentifier(), 1115 Typename2->getIdentifier())) 1116 return false; 1117 1118 break; 1119 } 1120 1121 case Type::DependentTemplateSpecialization: { 1122 const auto *Spec1 = cast<DependentTemplateSpecializationType>(T1); 1123 const auto *Spec2 = cast<DependentTemplateSpecializationType>(T2); 1124 if (!IsStructurallyEquivalent(Context, Spec1->getQualifier(), 1125 Spec2->getQualifier())) 1126 return false; 1127 if (!IsStructurallyEquivalent(Spec1->getIdentifier(), 1128 Spec2->getIdentifier())) 1129 return false; 1130 if (Spec1->getNumArgs() != Spec2->getNumArgs()) 1131 return false; 1132 for (unsigned I = 0, N = Spec1->getNumArgs(); I != N; ++I) { 1133 if (!IsStructurallyEquivalent(Context, Spec1->getArg(I), 1134 Spec2->getArg(I))) 1135 return false; 1136 } 1137 break; 1138 } 1139 1140 case Type::PackExpansion: 1141 if (!IsStructurallyEquivalent(Context, 1142 cast<PackExpansionType>(T1)->getPattern(), 1143 cast<PackExpansionType>(T2)->getPattern())) 1144 return false; 1145 break; 1146 1147 case Type::ObjCInterface: { 1148 const auto *Iface1 = cast<ObjCInterfaceType>(T1); 1149 const auto *Iface2 = cast<ObjCInterfaceType>(T2); 1150 if (!IsStructurallyEquivalent(Context, Iface1->getDecl(), 1151 Iface2->getDecl())) 1152 return false; 1153 break; 1154 } 1155 1156 case Type::ObjCTypeParam: { 1157 const auto *Obj1 = cast<ObjCTypeParamType>(T1); 1158 const auto *Obj2 = cast<ObjCTypeParamType>(T2); 1159 if (!IsStructurallyEquivalent(Context, Obj1->getDecl(), Obj2->getDecl())) 1160 return false; 1161 1162 if (Obj1->getNumProtocols() != Obj2->getNumProtocols()) 1163 return false; 1164 for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) { 1165 if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I), 1166 Obj2->getProtocol(I))) 1167 return false; 1168 } 1169 break; 1170 } 1171 1172 case Type::ObjCObject: { 1173 const auto *Obj1 = cast<ObjCObjectType>(T1); 1174 const auto *Obj2 = cast<ObjCObjectType>(T2); 1175 if (!IsStructurallyEquivalent(Context, Obj1->getBaseType(), 1176 Obj2->getBaseType())) 1177 return false; 1178 if (Obj1->getNumProtocols() != Obj2->getNumProtocols()) 1179 return false; 1180 for (unsigned I = 0, N = Obj1->getNumProtocols(); I != N; ++I) { 1181 if (!IsStructurallyEquivalent(Context, Obj1->getProtocol(I), 1182 Obj2->getProtocol(I))) 1183 return false; 1184 } 1185 break; 1186 } 1187 1188 case Type::ObjCObjectPointer: { 1189 const auto *Ptr1 = cast<ObjCObjectPointerType>(T1); 1190 const auto *Ptr2 = cast<ObjCObjectPointerType>(T2); 1191 if (!IsStructurallyEquivalent(Context, Ptr1->getPointeeType(), 1192 Ptr2->getPointeeType())) 1193 return false; 1194 break; 1195 } 1196 1197 case Type::Atomic: 1198 if (!IsStructurallyEquivalent(Context, cast<AtomicType>(T1)->getValueType(), 1199 cast<AtomicType>(T2)->getValueType())) 1200 return false; 1201 break; 1202 1203 case Type::Pipe: 1204 if (!IsStructurallyEquivalent(Context, cast<PipeType>(T1)->getElementType(), 1205 cast<PipeType>(T2)->getElementType())) 1206 return false; 1207 break; 1208 case Type::ExtInt: { 1209 const auto *Int1 = cast<ExtIntType>(T1); 1210 const auto *Int2 = cast<ExtIntType>(T2); 1211 1212 if (Int1->isUnsigned() != Int2->isUnsigned() || 1213 Int1->getNumBits() != Int2->getNumBits()) 1214 return false; 1215 break; 1216 } 1217 case Type::DependentExtInt: { 1218 const auto *Int1 = cast<DependentExtIntType>(T1); 1219 const auto *Int2 = cast<DependentExtIntType>(T2); 1220 1221 if (Int1->isUnsigned() != Int2->isUnsigned() || 1222 !IsStructurallyEquivalent(Context, Int1->getNumBitsExpr(), 1223 Int2->getNumBitsExpr())) 1224 return false; 1225 } 1226 } // end switch 1227 1228 return true; 1229 } 1230 1231 /// Determine structural equivalence of two fields. 1232 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1233 FieldDecl *Field1, FieldDecl *Field2) { 1234 const auto *Owner2 = cast<RecordDecl>(Field2->getDeclContext()); 1235 1236 // For anonymous structs/unions, match up the anonymous struct/union type 1237 // declarations directly, so that we don't go off searching for anonymous 1238 // types 1239 if (Field1->isAnonymousStructOrUnion() && 1240 Field2->isAnonymousStructOrUnion()) { 1241 RecordDecl *D1 = Field1->getType()->castAs<RecordType>()->getDecl(); 1242 RecordDecl *D2 = Field2->getType()->castAs<RecordType>()->getDecl(); 1243 return IsStructurallyEquivalent(Context, D1, D2); 1244 } 1245 1246 // Check for equivalent field names. 1247 IdentifierInfo *Name1 = Field1->getIdentifier(); 1248 IdentifierInfo *Name2 = Field2->getIdentifier(); 1249 if (!::IsStructurallyEquivalent(Name1, Name2)) { 1250 if (Context.Complain) { 1251 Context.Diag2( 1252 Owner2->getLocation(), 1253 Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent)) 1254 << Context.ToCtx.getTypeDeclType(Owner2); 1255 Context.Diag2(Field2->getLocation(), diag::note_odr_field_name) 1256 << Field2->getDeclName(); 1257 Context.Diag1(Field1->getLocation(), diag::note_odr_field_name) 1258 << Field1->getDeclName(); 1259 } 1260 return false; 1261 } 1262 1263 if (!IsStructurallyEquivalent(Context, Field1->getType(), 1264 Field2->getType())) { 1265 if (Context.Complain) { 1266 Context.Diag2( 1267 Owner2->getLocation(), 1268 Context.getApplicableDiagnostic(diag::err_odr_tag_type_inconsistent)) 1269 << Context.ToCtx.getTypeDeclType(Owner2); 1270 Context.Diag2(Field2->getLocation(), diag::note_odr_field) 1271 << Field2->getDeclName() << Field2->getType(); 1272 Context.Diag1(Field1->getLocation(), diag::note_odr_field) 1273 << Field1->getDeclName() << Field1->getType(); 1274 } 1275 return false; 1276 } 1277 1278 if (Field1->isBitField()) 1279 return IsStructurallyEquivalent(Context, Field1->getBitWidth(), 1280 Field2->getBitWidth()); 1281 1282 return true; 1283 } 1284 1285 /// Determine structural equivalence of two methods. 1286 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1287 CXXMethodDecl *Method1, 1288 CXXMethodDecl *Method2) { 1289 bool PropertiesEqual = 1290 Method1->getDeclKind() == Method2->getDeclKind() && 1291 Method1->getRefQualifier() == Method2->getRefQualifier() && 1292 Method1->getAccess() == Method2->getAccess() && 1293 Method1->getOverloadedOperator() == Method2->getOverloadedOperator() && 1294 Method1->isStatic() == Method2->isStatic() && 1295 Method1->isConst() == Method2->isConst() && 1296 Method1->isVolatile() == Method2->isVolatile() && 1297 Method1->isVirtual() == Method2->isVirtual() && 1298 Method1->isPure() == Method2->isPure() && 1299 Method1->isDefaulted() == Method2->isDefaulted() && 1300 Method1->isDeleted() == Method2->isDeleted(); 1301 if (!PropertiesEqual) 1302 return false; 1303 // FIXME: Check for 'final'. 1304 1305 if (auto *Constructor1 = dyn_cast<CXXConstructorDecl>(Method1)) { 1306 auto *Constructor2 = cast<CXXConstructorDecl>(Method2); 1307 if (!Constructor1->getExplicitSpecifier().isEquivalent( 1308 Constructor2->getExplicitSpecifier())) 1309 return false; 1310 } 1311 1312 if (auto *Conversion1 = dyn_cast<CXXConversionDecl>(Method1)) { 1313 auto *Conversion2 = cast<CXXConversionDecl>(Method2); 1314 if (!Conversion1->getExplicitSpecifier().isEquivalent( 1315 Conversion2->getExplicitSpecifier())) 1316 return false; 1317 if (!IsStructurallyEquivalent(Context, Conversion1->getConversionType(), 1318 Conversion2->getConversionType())) 1319 return false; 1320 } 1321 1322 const IdentifierInfo *Name1 = Method1->getIdentifier(); 1323 const IdentifierInfo *Name2 = Method2->getIdentifier(); 1324 if (!::IsStructurallyEquivalent(Name1, Name2)) { 1325 return false; 1326 // TODO: Names do not match, add warning like at check for FieldDecl. 1327 } 1328 1329 // Check the prototypes. 1330 if (!::IsStructurallyEquivalent(Context, 1331 Method1->getType(), Method2->getType())) 1332 return false; 1333 1334 return true; 1335 } 1336 1337 /// Determine structural equivalence of two lambda classes. 1338 static bool 1339 IsStructurallyEquivalentLambdas(StructuralEquivalenceContext &Context, 1340 CXXRecordDecl *D1, CXXRecordDecl *D2) { 1341 assert(D1->isLambda() && D2->isLambda() && 1342 "Must be called on lambda classes"); 1343 if (!IsStructurallyEquivalent(Context, D1->getLambdaCallOperator(), 1344 D2->getLambdaCallOperator())) 1345 return false; 1346 1347 return true; 1348 } 1349 1350 /// Determine structural equivalence of two records. 1351 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1352 RecordDecl *D1, RecordDecl *D2) { 1353 1354 // Check for equivalent structure names. 1355 IdentifierInfo *Name1 = D1->getIdentifier(); 1356 if (!Name1 && D1->getTypedefNameForAnonDecl()) 1357 Name1 = D1->getTypedefNameForAnonDecl()->getIdentifier(); 1358 IdentifierInfo *Name2 = D2->getIdentifier(); 1359 if (!Name2 && D2->getTypedefNameForAnonDecl()) 1360 Name2 = D2->getTypedefNameForAnonDecl()->getIdentifier(); 1361 if (!IsStructurallyEquivalent(Name1, Name2)) 1362 return false; 1363 1364 if (D1->isUnion() != D2->isUnion()) { 1365 if (Context.Complain) { 1366 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic( 1367 diag::err_odr_tag_type_inconsistent)) 1368 << Context.ToCtx.getTypeDeclType(D2); 1369 Context.Diag1(D1->getLocation(), diag::note_odr_tag_kind_here) 1370 << D1->getDeclName() << (unsigned)D1->getTagKind(); 1371 } 1372 return false; 1373 } 1374 1375 if (!D1->getDeclName() && !D2->getDeclName()) { 1376 // If both anonymous structs/unions are in a record context, make sure 1377 // they occur in the same location in the context records. 1378 if (Optional<unsigned> Index1 = 1379 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(D1)) { 1380 if (Optional<unsigned> Index2 = 1381 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex( 1382 D2)) { 1383 if (*Index1 != *Index2) 1384 return false; 1385 } 1386 } 1387 } 1388 1389 // If both declarations are class template specializations, we know 1390 // the ODR applies, so check the template and template arguments. 1391 const auto *Spec1 = dyn_cast<ClassTemplateSpecializationDecl>(D1); 1392 const auto *Spec2 = dyn_cast<ClassTemplateSpecializationDecl>(D2); 1393 if (Spec1 && Spec2) { 1394 // Check that the specialized templates are the same. 1395 if (!IsStructurallyEquivalent(Context, Spec1->getSpecializedTemplate(), 1396 Spec2->getSpecializedTemplate())) 1397 return false; 1398 1399 // Check that the template arguments are the same. 1400 if (Spec1->getTemplateArgs().size() != Spec2->getTemplateArgs().size()) 1401 return false; 1402 1403 for (unsigned I = 0, N = Spec1->getTemplateArgs().size(); I != N; ++I) 1404 if (!IsStructurallyEquivalent(Context, Spec1->getTemplateArgs().get(I), 1405 Spec2->getTemplateArgs().get(I))) 1406 return false; 1407 } 1408 // If one is a class template specialization and the other is not, these 1409 // structures are different. 1410 else if (Spec1 || Spec2) 1411 return false; 1412 1413 // Compare the definitions of these two records. If either or both are 1414 // incomplete (i.e. it is a forward decl), we assume that they are 1415 // equivalent. 1416 D1 = D1->getDefinition(); 1417 D2 = D2->getDefinition(); 1418 if (!D1 || !D2) 1419 return true; 1420 1421 // If any of the records has external storage and we do a minimal check (or 1422 // AST import) we assume they are equivalent. (If we didn't have this 1423 // assumption then `RecordDecl::LoadFieldsFromExternalStorage` could trigger 1424 // another AST import which in turn would call the structural equivalency 1425 // check again and finally we'd have an improper result.) 1426 if (Context.EqKind == StructuralEquivalenceKind::Minimal) 1427 if (D1->hasExternalLexicalStorage() || D2->hasExternalLexicalStorage()) 1428 return true; 1429 1430 // If one definition is currently being defined, we do not compare for 1431 // equality and we assume that the decls are equal. 1432 if (D1->isBeingDefined() || D2->isBeingDefined()) 1433 return true; 1434 1435 if (auto *D1CXX = dyn_cast<CXXRecordDecl>(D1)) { 1436 if (auto *D2CXX = dyn_cast<CXXRecordDecl>(D2)) { 1437 if (D1CXX->hasExternalLexicalStorage() && 1438 !D1CXX->isCompleteDefinition()) { 1439 D1CXX->getASTContext().getExternalSource()->CompleteType(D1CXX); 1440 } 1441 1442 if (D1CXX->isLambda() != D2CXX->isLambda()) 1443 return false; 1444 if (D1CXX->isLambda()) { 1445 if (!IsStructurallyEquivalentLambdas(Context, D1CXX, D2CXX)) 1446 return false; 1447 } 1448 1449 if (D1CXX->getNumBases() != D2CXX->getNumBases()) { 1450 if (Context.Complain) { 1451 Context.Diag2(D2->getLocation(), 1452 Context.getApplicableDiagnostic( 1453 diag::err_odr_tag_type_inconsistent)) 1454 << Context.ToCtx.getTypeDeclType(D2); 1455 Context.Diag2(D2->getLocation(), diag::note_odr_number_of_bases) 1456 << D2CXX->getNumBases(); 1457 Context.Diag1(D1->getLocation(), diag::note_odr_number_of_bases) 1458 << D1CXX->getNumBases(); 1459 } 1460 return false; 1461 } 1462 1463 // Check the base classes. 1464 for (CXXRecordDecl::base_class_iterator Base1 = D1CXX->bases_begin(), 1465 BaseEnd1 = D1CXX->bases_end(), 1466 Base2 = D2CXX->bases_begin(); 1467 Base1 != BaseEnd1; ++Base1, ++Base2) { 1468 if (!IsStructurallyEquivalent(Context, Base1->getType(), 1469 Base2->getType())) { 1470 if (Context.Complain) { 1471 Context.Diag2(D2->getLocation(), 1472 Context.getApplicableDiagnostic( 1473 diag::err_odr_tag_type_inconsistent)) 1474 << Context.ToCtx.getTypeDeclType(D2); 1475 Context.Diag2(Base2->getBeginLoc(), diag::note_odr_base) 1476 << Base2->getType() << Base2->getSourceRange(); 1477 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base) 1478 << Base1->getType() << Base1->getSourceRange(); 1479 } 1480 return false; 1481 } 1482 1483 // Check virtual vs. non-virtual inheritance mismatch. 1484 if (Base1->isVirtual() != Base2->isVirtual()) { 1485 if (Context.Complain) { 1486 Context.Diag2(D2->getLocation(), 1487 Context.getApplicableDiagnostic( 1488 diag::err_odr_tag_type_inconsistent)) 1489 << Context.ToCtx.getTypeDeclType(D2); 1490 Context.Diag2(Base2->getBeginLoc(), diag::note_odr_virtual_base) 1491 << Base2->isVirtual() << Base2->getSourceRange(); 1492 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base) 1493 << Base1->isVirtual() << Base1->getSourceRange(); 1494 } 1495 return false; 1496 } 1497 } 1498 1499 // Check the friends for consistency. 1500 CXXRecordDecl::friend_iterator Friend2 = D2CXX->friend_begin(), 1501 Friend2End = D2CXX->friend_end(); 1502 for (CXXRecordDecl::friend_iterator Friend1 = D1CXX->friend_begin(), 1503 Friend1End = D1CXX->friend_end(); 1504 Friend1 != Friend1End; ++Friend1, ++Friend2) { 1505 if (Friend2 == Friend2End) { 1506 if (Context.Complain) { 1507 Context.Diag2(D2->getLocation(), 1508 Context.getApplicableDiagnostic( 1509 diag::err_odr_tag_type_inconsistent)) 1510 << Context.ToCtx.getTypeDeclType(D2CXX); 1511 Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend); 1512 Context.Diag2(D2->getLocation(), diag::note_odr_missing_friend); 1513 } 1514 return false; 1515 } 1516 1517 if (!IsStructurallyEquivalent(Context, *Friend1, *Friend2)) { 1518 if (Context.Complain) { 1519 Context.Diag2(D2->getLocation(), 1520 Context.getApplicableDiagnostic( 1521 diag::err_odr_tag_type_inconsistent)) 1522 << Context.ToCtx.getTypeDeclType(D2CXX); 1523 Context.Diag1((*Friend1)->getFriendLoc(), diag::note_odr_friend); 1524 Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend); 1525 } 1526 return false; 1527 } 1528 } 1529 1530 if (Friend2 != Friend2End) { 1531 if (Context.Complain) { 1532 Context.Diag2(D2->getLocation(), 1533 Context.getApplicableDiagnostic( 1534 diag::err_odr_tag_type_inconsistent)) 1535 << Context.ToCtx.getTypeDeclType(D2); 1536 Context.Diag2((*Friend2)->getFriendLoc(), diag::note_odr_friend); 1537 Context.Diag1(D1->getLocation(), diag::note_odr_missing_friend); 1538 } 1539 return false; 1540 } 1541 } else if (D1CXX->getNumBases() > 0) { 1542 if (Context.Complain) { 1543 Context.Diag2(D2->getLocation(), 1544 Context.getApplicableDiagnostic( 1545 diag::err_odr_tag_type_inconsistent)) 1546 << Context.ToCtx.getTypeDeclType(D2); 1547 const CXXBaseSpecifier *Base1 = D1CXX->bases_begin(); 1548 Context.Diag1(Base1->getBeginLoc(), diag::note_odr_base) 1549 << Base1->getType() << Base1->getSourceRange(); 1550 Context.Diag2(D2->getLocation(), diag::note_odr_missing_base); 1551 } 1552 return false; 1553 } 1554 } 1555 1556 // Check the fields for consistency. 1557 RecordDecl::field_iterator Field2 = D2->field_begin(), 1558 Field2End = D2->field_end(); 1559 for (RecordDecl::field_iterator Field1 = D1->field_begin(), 1560 Field1End = D1->field_end(); 1561 Field1 != Field1End; ++Field1, ++Field2) { 1562 if (Field2 == Field2End) { 1563 if (Context.Complain) { 1564 Context.Diag2(D2->getLocation(), 1565 Context.getApplicableDiagnostic( 1566 diag::err_odr_tag_type_inconsistent)) 1567 << Context.ToCtx.getTypeDeclType(D2); 1568 Context.Diag1(Field1->getLocation(), diag::note_odr_field) 1569 << Field1->getDeclName() << Field1->getType(); 1570 Context.Diag2(D2->getLocation(), diag::note_odr_missing_field); 1571 } 1572 return false; 1573 } 1574 1575 if (!IsStructurallyEquivalent(Context, *Field1, *Field2)) 1576 return false; 1577 } 1578 1579 if (Field2 != Field2End) { 1580 if (Context.Complain) { 1581 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic( 1582 diag::err_odr_tag_type_inconsistent)) 1583 << Context.ToCtx.getTypeDeclType(D2); 1584 Context.Diag2(Field2->getLocation(), diag::note_odr_field) 1585 << Field2->getDeclName() << Field2->getType(); 1586 Context.Diag1(D1->getLocation(), diag::note_odr_missing_field); 1587 } 1588 return false; 1589 } 1590 1591 return true; 1592 } 1593 1594 /// Determine structural equivalence of two enums. 1595 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1596 EnumDecl *D1, EnumDecl *D2) { 1597 1598 // Check for equivalent enum names. 1599 IdentifierInfo *Name1 = D1->getIdentifier(); 1600 if (!Name1 && D1->getTypedefNameForAnonDecl()) 1601 Name1 = D1->getTypedefNameForAnonDecl()->getIdentifier(); 1602 IdentifierInfo *Name2 = D2->getIdentifier(); 1603 if (!Name2 && D2->getTypedefNameForAnonDecl()) 1604 Name2 = D2->getTypedefNameForAnonDecl()->getIdentifier(); 1605 if (!IsStructurallyEquivalent(Name1, Name2)) 1606 return false; 1607 1608 // Compare the definitions of these two enums. If either or both are 1609 // incomplete (i.e. forward declared), we assume that they are equivalent. 1610 D1 = D1->getDefinition(); 1611 D2 = D2->getDefinition(); 1612 if (!D1 || !D2) 1613 return true; 1614 1615 EnumDecl::enumerator_iterator EC2 = D2->enumerator_begin(), 1616 EC2End = D2->enumerator_end(); 1617 for (EnumDecl::enumerator_iterator EC1 = D1->enumerator_begin(), 1618 EC1End = D1->enumerator_end(); 1619 EC1 != EC1End; ++EC1, ++EC2) { 1620 if (EC2 == EC2End) { 1621 if (Context.Complain) { 1622 Context.Diag2(D2->getLocation(), 1623 Context.getApplicableDiagnostic( 1624 diag::err_odr_tag_type_inconsistent)) 1625 << Context.ToCtx.getTypeDeclType(D2); 1626 Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator) 1627 << EC1->getDeclName() << toString(EC1->getInitVal(), 10); 1628 Context.Diag2(D2->getLocation(), diag::note_odr_missing_enumerator); 1629 } 1630 return false; 1631 } 1632 1633 llvm::APSInt Val1 = EC1->getInitVal(); 1634 llvm::APSInt Val2 = EC2->getInitVal(); 1635 if (!llvm::APSInt::isSameValue(Val1, Val2) || 1636 !IsStructurallyEquivalent(EC1->getIdentifier(), EC2->getIdentifier())) { 1637 if (Context.Complain) { 1638 Context.Diag2(D2->getLocation(), 1639 Context.getApplicableDiagnostic( 1640 diag::err_odr_tag_type_inconsistent)) 1641 << Context.ToCtx.getTypeDeclType(D2); 1642 Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator) 1643 << EC2->getDeclName() << toString(EC2->getInitVal(), 10); 1644 Context.Diag1(EC1->getLocation(), diag::note_odr_enumerator) 1645 << EC1->getDeclName() << toString(EC1->getInitVal(), 10); 1646 } 1647 return false; 1648 } 1649 } 1650 1651 if (EC2 != EC2End) { 1652 if (Context.Complain) { 1653 Context.Diag2(D2->getLocation(), Context.getApplicableDiagnostic( 1654 diag::err_odr_tag_type_inconsistent)) 1655 << Context.ToCtx.getTypeDeclType(D2); 1656 Context.Diag2(EC2->getLocation(), diag::note_odr_enumerator) 1657 << EC2->getDeclName() << toString(EC2->getInitVal(), 10); 1658 Context.Diag1(D1->getLocation(), diag::note_odr_missing_enumerator); 1659 } 1660 return false; 1661 } 1662 1663 return true; 1664 } 1665 1666 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1667 TemplateParameterList *Params1, 1668 TemplateParameterList *Params2) { 1669 if (Params1->size() != Params2->size()) { 1670 if (Context.Complain) { 1671 Context.Diag2(Params2->getTemplateLoc(), 1672 Context.getApplicableDiagnostic( 1673 diag::err_odr_different_num_template_parameters)) 1674 << Params1->size() << Params2->size(); 1675 Context.Diag1(Params1->getTemplateLoc(), 1676 diag::note_odr_template_parameter_list); 1677 } 1678 return false; 1679 } 1680 1681 for (unsigned I = 0, N = Params1->size(); I != N; ++I) { 1682 if (Params1->getParam(I)->getKind() != Params2->getParam(I)->getKind()) { 1683 if (Context.Complain) { 1684 Context.Diag2(Params2->getParam(I)->getLocation(), 1685 Context.getApplicableDiagnostic( 1686 diag::err_odr_different_template_parameter_kind)); 1687 Context.Diag1(Params1->getParam(I)->getLocation(), 1688 diag::note_odr_template_parameter_here); 1689 } 1690 return false; 1691 } 1692 1693 if (!IsStructurallyEquivalent(Context, Params1->getParam(I), 1694 Params2->getParam(I))) 1695 return false; 1696 } 1697 1698 return true; 1699 } 1700 1701 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1702 TemplateTypeParmDecl *D1, 1703 TemplateTypeParmDecl *D2) { 1704 if (D1->isParameterPack() != D2->isParameterPack()) { 1705 if (Context.Complain) { 1706 Context.Diag2(D2->getLocation(), 1707 Context.getApplicableDiagnostic( 1708 diag::err_odr_parameter_pack_non_pack)) 1709 << D2->isParameterPack(); 1710 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack) 1711 << D1->isParameterPack(); 1712 } 1713 return false; 1714 } 1715 1716 return true; 1717 } 1718 1719 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1720 NonTypeTemplateParmDecl *D1, 1721 NonTypeTemplateParmDecl *D2) { 1722 if (D1->isParameterPack() != D2->isParameterPack()) { 1723 if (Context.Complain) { 1724 Context.Diag2(D2->getLocation(), 1725 Context.getApplicableDiagnostic( 1726 diag::err_odr_parameter_pack_non_pack)) 1727 << D2->isParameterPack(); 1728 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack) 1729 << D1->isParameterPack(); 1730 } 1731 return false; 1732 } 1733 1734 // Check types. 1735 if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) { 1736 if (Context.Complain) { 1737 Context.Diag2(D2->getLocation(), 1738 Context.getApplicableDiagnostic( 1739 diag::err_odr_non_type_parameter_type_inconsistent)) 1740 << D2->getType() << D1->getType(); 1741 Context.Diag1(D1->getLocation(), diag::note_odr_value_here) 1742 << D1->getType(); 1743 } 1744 return false; 1745 } 1746 1747 return true; 1748 } 1749 1750 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1751 TemplateTemplateParmDecl *D1, 1752 TemplateTemplateParmDecl *D2) { 1753 if (D1->isParameterPack() != D2->isParameterPack()) { 1754 if (Context.Complain) { 1755 Context.Diag2(D2->getLocation(), 1756 Context.getApplicableDiagnostic( 1757 diag::err_odr_parameter_pack_non_pack)) 1758 << D2->isParameterPack(); 1759 Context.Diag1(D1->getLocation(), diag::note_odr_parameter_pack_non_pack) 1760 << D1->isParameterPack(); 1761 } 1762 return false; 1763 } 1764 1765 // Check template parameter lists. 1766 return IsStructurallyEquivalent(Context, D1->getTemplateParameters(), 1767 D2->getTemplateParameters()); 1768 } 1769 1770 static bool IsTemplateDeclCommonStructurallyEquivalent( 1771 StructuralEquivalenceContext &Ctx, TemplateDecl *D1, TemplateDecl *D2) { 1772 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier())) 1773 return false; 1774 if (!D1->getIdentifier()) // Special name 1775 if (D1->getNameAsString() != D2->getNameAsString()) 1776 return false; 1777 return IsStructurallyEquivalent(Ctx, D1->getTemplateParameters(), 1778 D2->getTemplateParameters()); 1779 } 1780 1781 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1782 ClassTemplateDecl *D1, 1783 ClassTemplateDecl *D2) { 1784 // Check template parameters. 1785 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2)) 1786 return false; 1787 1788 // Check the templated declaration. 1789 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl(), 1790 D2->getTemplatedDecl()); 1791 } 1792 1793 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1794 FunctionTemplateDecl *D1, 1795 FunctionTemplateDecl *D2) { 1796 // Check template parameters. 1797 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2)) 1798 return false; 1799 1800 // Check the templated declaration. 1801 return IsStructurallyEquivalent(Context, D1->getTemplatedDecl()->getType(), 1802 D2->getTemplatedDecl()->getType()); 1803 } 1804 1805 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1806 ConceptDecl *D1, 1807 ConceptDecl *D2) { 1808 // Check template parameters. 1809 if (!IsTemplateDeclCommonStructurallyEquivalent(Context, D1, D2)) 1810 return false; 1811 1812 // Check the constraint expression. 1813 return IsStructurallyEquivalent(Context, D1->getConstraintExpr(), 1814 D2->getConstraintExpr()); 1815 } 1816 1817 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1818 FriendDecl *D1, FriendDecl *D2) { 1819 if ((D1->getFriendType() && D2->getFriendDecl()) || 1820 (D1->getFriendDecl() && D2->getFriendType())) { 1821 return false; 1822 } 1823 if (D1->getFriendType() && D2->getFriendType()) 1824 return IsStructurallyEquivalent(Context, 1825 D1->getFriendType()->getType(), 1826 D2->getFriendType()->getType()); 1827 if (D1->getFriendDecl() && D2->getFriendDecl()) 1828 return IsStructurallyEquivalent(Context, D1->getFriendDecl(), 1829 D2->getFriendDecl()); 1830 return false; 1831 } 1832 1833 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1834 TypedefNameDecl *D1, TypedefNameDecl *D2) { 1835 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier())) 1836 return false; 1837 1838 return IsStructurallyEquivalent(Context, D1->getUnderlyingType(), 1839 D2->getUnderlyingType()); 1840 } 1841 1842 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1843 FunctionDecl *D1, FunctionDecl *D2) { 1844 if (!IsStructurallyEquivalent(D1->getIdentifier(), D2->getIdentifier())) 1845 return false; 1846 1847 if (D1->isOverloadedOperator()) { 1848 if (!D2->isOverloadedOperator()) 1849 return false; 1850 if (D1->getOverloadedOperator() != D2->getOverloadedOperator()) 1851 return false; 1852 } 1853 1854 // FIXME: Consider checking for function attributes as well. 1855 if (!IsStructurallyEquivalent(Context, D1->getType(), D2->getType())) 1856 return false; 1857 1858 return true; 1859 } 1860 1861 /// Determine structural equivalence of two declarations. 1862 static bool IsStructurallyEquivalent(StructuralEquivalenceContext &Context, 1863 Decl *D1, Decl *D2) { 1864 // FIXME: Check for known structural equivalences via a callback of some sort. 1865 1866 D1 = D1->getCanonicalDecl(); 1867 D2 = D2->getCanonicalDecl(); 1868 std::pair<Decl *, Decl *> P{D1, D2}; 1869 1870 // Check whether we already know that these two declarations are not 1871 // structurally equivalent. 1872 if (Context.NonEquivalentDecls.count(P)) 1873 return false; 1874 1875 // Check if a check for these declarations is already pending. 1876 // If yes D1 and D2 will be checked later (from DeclsToCheck), 1877 // or these are already checked (and equivalent). 1878 bool Inserted = Context.VisitedDecls.insert(P).second; 1879 if (!Inserted) 1880 return true; 1881 1882 Context.DeclsToCheck.push(P); 1883 1884 return true; 1885 } 1886 1887 DiagnosticBuilder StructuralEquivalenceContext::Diag1(SourceLocation Loc, 1888 unsigned DiagID) { 1889 assert(Complain && "Not allowed to complain"); 1890 if (LastDiagFromC2) 1891 FromCtx.getDiagnostics().notePriorDiagnosticFrom(ToCtx.getDiagnostics()); 1892 LastDiagFromC2 = false; 1893 return FromCtx.getDiagnostics().Report(Loc, DiagID); 1894 } 1895 1896 DiagnosticBuilder StructuralEquivalenceContext::Diag2(SourceLocation Loc, 1897 unsigned DiagID) { 1898 assert(Complain && "Not allowed to complain"); 1899 if (!LastDiagFromC2) 1900 ToCtx.getDiagnostics().notePriorDiagnosticFrom(FromCtx.getDiagnostics()); 1901 LastDiagFromC2 = true; 1902 return ToCtx.getDiagnostics().Report(Loc, DiagID); 1903 } 1904 1905 Optional<unsigned> 1906 StructuralEquivalenceContext::findUntaggedStructOrUnionIndex(RecordDecl *Anon) { 1907 ASTContext &Context = Anon->getASTContext(); 1908 QualType AnonTy = Context.getRecordType(Anon); 1909 1910 const auto *Owner = dyn_cast<RecordDecl>(Anon->getDeclContext()); 1911 if (!Owner) 1912 return None; 1913 1914 unsigned Index = 0; 1915 for (const auto *D : Owner->noload_decls()) { 1916 const auto *F = dyn_cast<FieldDecl>(D); 1917 if (!F) 1918 continue; 1919 1920 if (F->isAnonymousStructOrUnion()) { 1921 if (Context.hasSameType(F->getType(), AnonTy)) 1922 break; 1923 ++Index; 1924 continue; 1925 } 1926 1927 // If the field looks like this: 1928 // struct { ... } A; 1929 QualType FieldType = F->getType(); 1930 // In case of nested structs. 1931 while (const auto *ElabType = dyn_cast<ElaboratedType>(FieldType)) 1932 FieldType = ElabType->getNamedType(); 1933 1934 if (const auto *RecType = dyn_cast<RecordType>(FieldType)) { 1935 const RecordDecl *RecDecl = RecType->getDecl(); 1936 if (RecDecl->getDeclContext() == Owner && !RecDecl->getIdentifier()) { 1937 if (Context.hasSameType(FieldType, AnonTy)) 1938 break; 1939 ++Index; 1940 continue; 1941 } 1942 } 1943 } 1944 1945 return Index; 1946 } 1947 1948 unsigned StructuralEquivalenceContext::getApplicableDiagnostic( 1949 unsigned ErrorDiagnostic) { 1950 if (ErrorOnTagTypeMismatch) 1951 return ErrorDiagnostic; 1952 1953 switch (ErrorDiagnostic) { 1954 case diag::err_odr_variable_type_inconsistent: 1955 return diag::warn_odr_variable_type_inconsistent; 1956 case diag::err_odr_variable_multiple_def: 1957 return diag::warn_odr_variable_multiple_def; 1958 case diag::err_odr_function_type_inconsistent: 1959 return diag::warn_odr_function_type_inconsistent; 1960 case diag::err_odr_tag_type_inconsistent: 1961 return diag::warn_odr_tag_type_inconsistent; 1962 case diag::err_odr_field_type_inconsistent: 1963 return diag::warn_odr_field_type_inconsistent; 1964 case diag::err_odr_ivar_type_inconsistent: 1965 return diag::warn_odr_ivar_type_inconsistent; 1966 case diag::err_odr_objc_superclass_inconsistent: 1967 return diag::warn_odr_objc_superclass_inconsistent; 1968 case diag::err_odr_objc_method_result_type_inconsistent: 1969 return diag::warn_odr_objc_method_result_type_inconsistent; 1970 case diag::err_odr_objc_method_num_params_inconsistent: 1971 return diag::warn_odr_objc_method_num_params_inconsistent; 1972 case diag::err_odr_objc_method_param_type_inconsistent: 1973 return diag::warn_odr_objc_method_param_type_inconsistent; 1974 case diag::err_odr_objc_method_variadic_inconsistent: 1975 return diag::warn_odr_objc_method_variadic_inconsistent; 1976 case diag::err_odr_objc_property_type_inconsistent: 1977 return diag::warn_odr_objc_property_type_inconsistent; 1978 case diag::err_odr_objc_property_impl_kind_inconsistent: 1979 return diag::warn_odr_objc_property_impl_kind_inconsistent; 1980 case diag::err_odr_objc_synthesize_ivar_inconsistent: 1981 return diag::warn_odr_objc_synthesize_ivar_inconsistent; 1982 case diag::err_odr_different_num_template_parameters: 1983 return diag::warn_odr_different_num_template_parameters; 1984 case diag::err_odr_different_template_parameter_kind: 1985 return diag::warn_odr_different_template_parameter_kind; 1986 case diag::err_odr_parameter_pack_non_pack: 1987 return diag::warn_odr_parameter_pack_non_pack; 1988 case diag::err_odr_non_type_parameter_type_inconsistent: 1989 return diag::warn_odr_non_type_parameter_type_inconsistent; 1990 } 1991 llvm_unreachable("Diagnostic kind not handled in preceding switch"); 1992 } 1993 1994 bool StructuralEquivalenceContext::IsEquivalent(Decl *D1, Decl *D2) { 1995 1996 // Ensure that the implementation functions (all static functions in this TU) 1997 // never call the public ASTStructuralEquivalence::IsEquivalent() functions, 1998 // because that will wreak havoc the internal state (DeclsToCheck and 1999 // VisitedDecls members) and can cause faulty behaviour. 2000 // In other words: Do not start a graph search from a new node with the 2001 // internal data of another search in progress. 2002 // FIXME: Better encapsulation and separation of internal and public 2003 // functionality. 2004 assert(DeclsToCheck.empty()); 2005 assert(VisitedDecls.empty()); 2006 2007 if (!::IsStructurallyEquivalent(*this, D1, D2)) 2008 return false; 2009 2010 return !Finish(); 2011 } 2012 2013 bool StructuralEquivalenceContext::IsEquivalent(QualType T1, QualType T2) { 2014 assert(DeclsToCheck.empty()); 2015 assert(VisitedDecls.empty()); 2016 if (!::IsStructurallyEquivalent(*this, T1, T2)) 2017 return false; 2018 2019 return !Finish(); 2020 } 2021 2022 bool StructuralEquivalenceContext::IsEquivalent(Stmt *S1, Stmt *S2) { 2023 assert(DeclsToCheck.empty()); 2024 assert(VisitedDecls.empty()); 2025 if (!::IsStructurallyEquivalent(*this, S1, S2)) 2026 return false; 2027 2028 return !Finish(); 2029 } 2030 2031 bool StructuralEquivalenceContext::CheckCommonEquivalence(Decl *D1, Decl *D2) { 2032 // Check for equivalent described template. 2033 TemplateDecl *Template1 = D1->getDescribedTemplate(); 2034 TemplateDecl *Template2 = D2->getDescribedTemplate(); 2035 if ((Template1 != nullptr) != (Template2 != nullptr)) 2036 return false; 2037 if (Template1 && !IsStructurallyEquivalent(*this, Template1, Template2)) 2038 return false; 2039 2040 // FIXME: Move check for identifier names into this function. 2041 2042 return true; 2043 } 2044 2045 bool StructuralEquivalenceContext::CheckKindSpecificEquivalence( 2046 Decl *D1, Decl *D2) { 2047 2048 // Kind mismatch. 2049 if (D1->getKind() != D2->getKind()) 2050 return false; 2051 2052 // Cast the Decls to their actual subclass so that the right overload of 2053 // IsStructurallyEquivalent is called. 2054 switch (D1->getKind()) { 2055 #define ABSTRACT_DECL(DECL) 2056 #define DECL(DERIVED, BASE) \ 2057 case Decl::Kind::DERIVED: \ 2058 return ::IsStructurallyEquivalent(*this, static_cast<DERIVED##Decl *>(D1), \ 2059 static_cast<DERIVED##Decl *>(D2)); 2060 #include "clang/AST/DeclNodes.inc" 2061 } 2062 return true; 2063 } 2064 2065 bool StructuralEquivalenceContext::Finish() { 2066 while (!DeclsToCheck.empty()) { 2067 // Check the next declaration. 2068 std::pair<Decl *, Decl *> P = DeclsToCheck.front(); 2069 DeclsToCheck.pop(); 2070 2071 Decl *D1 = P.first; 2072 Decl *D2 = P.second; 2073 2074 bool Equivalent = 2075 CheckCommonEquivalence(D1, D2) && CheckKindSpecificEquivalence(D1, D2); 2076 2077 if (!Equivalent) { 2078 // Note that these two declarations are not equivalent (and we already 2079 // know about it). 2080 NonEquivalentDecls.insert(P); 2081 2082 return true; 2083 } 2084 } 2085 2086 return false; 2087 } 2088