1 //===--- ASTDiagnostic.cpp - Diagnostic Printing Hooks for AST Nodes ------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements a diagnostic formatting hook for AST elements. 11 // 12 //===----------------------------------------------------------------------===// 13 #include "clang/AST/ASTDiagnostic.h" 14 #include "clang/AST/ASTContext.h" 15 #include "clang/AST/ASTLambda.h" 16 #include "clang/AST/Attr.h" 17 #include "clang/AST/DeclObjC.h" 18 #include "clang/AST/DeclTemplate.h" 19 #include "clang/AST/ExprCXX.h" 20 #include "clang/AST/TemplateBase.h" 21 #include "clang/AST/Type.h" 22 #include "llvm/ADT/SmallString.h" 23 #include "llvm/Support/raw_ostream.h" 24 25 using namespace clang; 26 27 // Returns a desugared version of the QualType, and marks ShouldAKA as true 28 // whenever we remove significant sugar from the type. 29 static QualType Desugar(ASTContext &Context, QualType QT, bool &ShouldAKA) { 30 QualifierCollector QC; 31 32 while (true) { 33 const Type *Ty = QC.strip(QT); 34 35 // Don't aka just because we saw an elaborated type... 36 if (const ElaboratedType *ET = dyn_cast<ElaboratedType>(Ty)) { 37 QT = ET->desugar(); 38 continue; 39 } 40 // ... or a paren type ... 41 if (const ParenType *PT = dyn_cast<ParenType>(Ty)) { 42 QT = PT->desugar(); 43 continue; 44 } 45 // ...or a substituted template type parameter ... 46 if (const SubstTemplateTypeParmType *ST = 47 dyn_cast<SubstTemplateTypeParmType>(Ty)) { 48 QT = ST->desugar(); 49 continue; 50 } 51 // ...or an attributed type... 52 if (const AttributedType *AT = dyn_cast<AttributedType>(Ty)) { 53 QT = AT->desugar(); 54 continue; 55 } 56 // ...or an adjusted type... 57 if (const AdjustedType *AT = dyn_cast<AdjustedType>(Ty)) { 58 QT = AT->desugar(); 59 continue; 60 } 61 // ... or an auto type. 62 if (const AutoType *AT = dyn_cast<AutoType>(Ty)) { 63 if (!AT->isSugared()) 64 break; 65 QT = AT->desugar(); 66 continue; 67 } 68 69 // Don't desugar template specializations, unless it's an alias template. 70 if (const TemplateSpecializationType *TST 71 = dyn_cast<TemplateSpecializationType>(Ty)) 72 if (!TST->isTypeAlias()) 73 break; 74 75 // Don't desugar magic Objective-C types. 76 if (QualType(Ty,0) == Context.getObjCIdType() || 77 QualType(Ty,0) == Context.getObjCClassType() || 78 QualType(Ty,0) == Context.getObjCSelType() || 79 QualType(Ty,0) == Context.getObjCProtoType()) 80 break; 81 82 // Don't desugar va_list. 83 if (QualType(Ty,0) == Context.getBuiltinVaListType()) 84 break; 85 86 // Otherwise, do a single-step desugar. 87 QualType Underlying; 88 bool IsSugar = false; 89 switch (Ty->getTypeClass()) { 90 #define ABSTRACT_TYPE(Class, Base) 91 #define TYPE(Class, Base) \ 92 case Type::Class: { \ 93 const Class##Type *CTy = cast<Class##Type>(Ty); \ 94 if (CTy->isSugared()) { \ 95 IsSugar = true; \ 96 Underlying = CTy->desugar(); \ 97 } \ 98 break; \ 99 } 100 #include "clang/AST/TypeNodes.def" 101 } 102 103 // If it wasn't sugared, we're done. 104 if (!IsSugar) 105 break; 106 107 // If the desugared type is a vector type, we don't want to expand 108 // it, it will turn into an attribute mess. People want their "vec4". 109 if (isa<VectorType>(Underlying)) 110 break; 111 112 // Don't desugar through the primary typedef of an anonymous type. 113 if (const TagType *UTT = Underlying->getAs<TagType>()) 114 if (const TypedefType *QTT = dyn_cast<TypedefType>(QT)) 115 if (UTT->getDecl()->getTypedefNameForAnonDecl() == QTT->getDecl()) 116 break; 117 118 // Record that we actually looked through an opaque type here. 119 ShouldAKA = true; 120 QT = Underlying; 121 } 122 123 // If we have a pointer-like type, desugar the pointee as well. 124 // FIXME: Handle other pointer-like types. 125 if (const PointerType *Ty = QT->getAs<PointerType>()) { 126 QT = Context.getPointerType(Desugar(Context, Ty->getPointeeType(), 127 ShouldAKA)); 128 } else if (const LValueReferenceType *Ty = QT->getAs<LValueReferenceType>()) { 129 QT = Context.getLValueReferenceType(Desugar(Context, Ty->getPointeeType(), 130 ShouldAKA)); 131 } else if (const RValueReferenceType *Ty = QT->getAs<RValueReferenceType>()) { 132 QT = Context.getRValueReferenceType(Desugar(Context, Ty->getPointeeType(), 133 ShouldAKA)); 134 } 135 136 return QC.apply(Context, QT); 137 } 138 139 /// \brief Convert the given type to a string suitable for printing as part of 140 /// a diagnostic. 141 /// 142 /// There are four main criteria when determining whether we should have an 143 /// a.k.a. clause when pretty-printing a type: 144 /// 145 /// 1) Some types provide very minimal sugar that doesn't impede the 146 /// user's understanding --- for example, elaborated type 147 /// specifiers. If this is all the sugar we see, we don't want an 148 /// a.k.a. clause. 149 /// 2) Some types are technically sugared but are much more familiar 150 /// when seen in their sugared form --- for example, va_list, 151 /// vector types, and the magic Objective C types. We don't 152 /// want to desugar these, even if we do produce an a.k.a. clause. 153 /// 3) Some types may have already been desugared previously in this diagnostic. 154 /// if this is the case, doing another "aka" would just be clutter. 155 /// 4) Two different types within the same diagnostic have the same output 156 /// string. In this case, force an a.k.a with the desugared type when 157 /// doing so will provide additional information. 158 /// 159 /// \param Context the context in which the type was allocated 160 /// \param Ty the type to print 161 /// \param QualTypeVals pointer values to QualTypes which are used in the 162 /// diagnostic message 163 static std::string 164 ConvertTypeToDiagnosticString(ASTContext &Context, QualType Ty, 165 ArrayRef<DiagnosticsEngine::ArgumentValue> PrevArgs, 166 ArrayRef<intptr_t> QualTypeVals) { 167 // FIXME: Playing with std::string is really slow. 168 bool ForceAKA = false; 169 QualType CanTy = Ty.getCanonicalType(); 170 std::string S = Ty.getAsString(Context.getPrintingPolicy()); 171 std::string CanS = CanTy.getAsString(Context.getPrintingPolicy()); 172 173 for (unsigned I = 0, E = QualTypeVals.size(); I != E; ++I) { 174 QualType CompareTy = 175 QualType::getFromOpaquePtr(reinterpret_cast<void*>(QualTypeVals[I])); 176 if (CompareTy.isNull()) 177 continue; 178 if (CompareTy == Ty) 179 continue; // Same types 180 QualType CompareCanTy = CompareTy.getCanonicalType(); 181 if (CompareCanTy == CanTy) 182 continue; // Same canonical types 183 std::string CompareS = CompareTy.getAsString(Context.getPrintingPolicy()); 184 bool aka; 185 QualType CompareDesugar = Desugar(Context, CompareTy, aka); 186 std::string CompareDesugarStr = 187 CompareDesugar.getAsString(Context.getPrintingPolicy()); 188 if (CompareS != S && CompareDesugarStr != S) 189 continue; // The type string is different than the comparison string 190 // and the desugared comparison string. 191 std::string CompareCanS = 192 CompareCanTy.getAsString(Context.getPrintingPolicy()); 193 194 if (CompareCanS == CanS) 195 continue; // No new info from canonical type 196 197 ForceAKA = true; 198 break; 199 } 200 201 // Check to see if we already desugared this type in this 202 // diagnostic. If so, don't do it again. 203 bool Repeated = false; 204 for (unsigned i = 0, e = PrevArgs.size(); i != e; ++i) { 205 // TODO: Handle ak_declcontext case. 206 if (PrevArgs[i].first == DiagnosticsEngine::ak_qualtype) { 207 void *Ptr = (void*)PrevArgs[i].second; 208 QualType PrevTy(QualType::getFromOpaquePtr(Ptr)); 209 if (PrevTy == Ty) { 210 Repeated = true; 211 break; 212 } 213 } 214 } 215 216 // Consider producing an a.k.a. clause if removing all the direct 217 // sugar gives us something "significantly different". 218 if (!Repeated) { 219 bool ShouldAKA = false; 220 QualType DesugaredTy = Desugar(Context, Ty, ShouldAKA); 221 if (ShouldAKA || ForceAKA) { 222 if (DesugaredTy == Ty) { 223 DesugaredTy = Ty.getCanonicalType(); 224 } 225 std::string akaStr = DesugaredTy.getAsString(Context.getPrintingPolicy()); 226 if (akaStr != S) { 227 S = "'" + S + "' (aka '" + akaStr + "')"; 228 return S; 229 } 230 } 231 232 // Give some additional info on vector types. These are either not desugared 233 // or displaying complex __attribute__ expressions so add details of the 234 // type and element count. 235 if (Ty->isVectorType()) { 236 const VectorType *VTy = Ty->getAs<VectorType>(); 237 std::string DecoratedString; 238 llvm::raw_string_ostream OS(DecoratedString); 239 const char *Values = VTy->getNumElements() > 1 ? "values" : "value"; 240 OS << "'" << S << "' (vector of " << VTy->getNumElements() << " '" 241 << VTy->getElementType().getAsString(Context.getPrintingPolicy()) 242 << "' " << Values << ")"; 243 return OS.str(); 244 } 245 } 246 247 S = "'" + S + "'"; 248 return S; 249 } 250 251 static bool FormatTemplateTypeDiff(ASTContext &Context, QualType FromType, 252 QualType ToType, bool PrintTree, 253 bool PrintFromType, bool ElideType, 254 bool ShowColors, raw_ostream &OS); 255 256 void clang::FormatASTNodeDiagnosticArgument( 257 DiagnosticsEngine::ArgumentKind Kind, 258 intptr_t Val, 259 StringRef Modifier, 260 StringRef Argument, 261 ArrayRef<DiagnosticsEngine::ArgumentValue> PrevArgs, 262 SmallVectorImpl<char> &Output, 263 void *Cookie, 264 ArrayRef<intptr_t> QualTypeVals) { 265 ASTContext &Context = *static_cast<ASTContext*>(Cookie); 266 267 size_t OldEnd = Output.size(); 268 llvm::raw_svector_ostream OS(Output); 269 bool NeedQuotes = true; 270 271 switch (Kind) { 272 default: llvm_unreachable("unknown ArgumentKind"); 273 case DiagnosticsEngine::ak_qualtype_pair: { 274 TemplateDiffTypes &TDT = *reinterpret_cast<TemplateDiffTypes*>(Val); 275 QualType FromType = 276 QualType::getFromOpaquePtr(reinterpret_cast<void*>(TDT.FromType)); 277 QualType ToType = 278 QualType::getFromOpaquePtr(reinterpret_cast<void*>(TDT.ToType)); 279 280 if (FormatTemplateTypeDiff(Context, FromType, ToType, TDT.PrintTree, 281 TDT.PrintFromType, TDT.ElideType, 282 TDT.ShowColors, OS)) { 283 NeedQuotes = !TDT.PrintTree; 284 TDT.TemplateDiffUsed = true; 285 break; 286 } 287 288 // Don't fall-back during tree printing. The caller will handle 289 // this case. 290 if (TDT.PrintTree) 291 return; 292 293 // Attempting to do a template diff on non-templates. Set the variables 294 // and continue with regular type printing of the appropriate type. 295 Val = TDT.PrintFromType ? TDT.FromType : TDT.ToType; 296 Modifier = StringRef(); 297 Argument = StringRef(); 298 // Fall through 299 } 300 case DiagnosticsEngine::ak_qualtype: { 301 assert(Modifier.empty() && Argument.empty() && 302 "Invalid modifier for QualType argument"); 303 304 QualType Ty(QualType::getFromOpaquePtr(reinterpret_cast<void*>(Val))); 305 OS << ConvertTypeToDiagnosticString(Context, Ty, PrevArgs, QualTypeVals); 306 NeedQuotes = false; 307 break; 308 } 309 case DiagnosticsEngine::ak_declarationname: { 310 if (Modifier == "objcclass" && Argument.empty()) 311 OS << '+'; 312 else if (Modifier == "objcinstance" && Argument.empty()) 313 OS << '-'; 314 else 315 assert(Modifier.empty() && Argument.empty() && 316 "Invalid modifier for DeclarationName argument"); 317 318 OS << DeclarationName::getFromOpaqueInteger(Val); 319 break; 320 } 321 case DiagnosticsEngine::ak_nameddecl: { 322 bool Qualified; 323 if (Modifier == "q" && Argument.empty()) 324 Qualified = true; 325 else { 326 assert(Modifier.empty() && Argument.empty() && 327 "Invalid modifier for NamedDecl* argument"); 328 Qualified = false; 329 } 330 const NamedDecl *ND = reinterpret_cast<const NamedDecl*>(Val); 331 ND->getNameForDiagnostic(OS, Context.getPrintingPolicy(), Qualified); 332 break; 333 } 334 case DiagnosticsEngine::ak_nestednamespec: { 335 NestedNameSpecifier *NNS = reinterpret_cast<NestedNameSpecifier*>(Val); 336 NNS->print(OS, Context.getPrintingPolicy()); 337 NeedQuotes = false; 338 break; 339 } 340 case DiagnosticsEngine::ak_declcontext: { 341 DeclContext *DC = reinterpret_cast<DeclContext *> (Val); 342 assert(DC && "Should never have a null declaration context"); 343 NeedQuotes = false; 344 345 if (DC->isTranslationUnit()) { 346 // FIXME: Get these strings from some localized place 347 if (Context.getLangOpts().CPlusPlus) 348 OS << "the global namespace"; 349 else 350 OS << "the global scope"; 351 } else if (TypeDecl *Type = dyn_cast<TypeDecl>(DC)) { 352 OS << ConvertTypeToDiagnosticString(Context, 353 Context.getTypeDeclType(Type), 354 PrevArgs, QualTypeVals); 355 } else { 356 // FIXME: Get these strings from some localized place 357 if (isa<BlockDecl>(DC)) { 358 OS << "block literal"; 359 break; 360 } 361 if (isLambdaCallOperator(DC)) { 362 OS << "lambda expression"; 363 break; 364 } 365 NamedDecl *ND = cast<NamedDecl>(DC); 366 if (isa<NamespaceDecl>(ND)) 367 OS << "namespace "; 368 else if (isa<ObjCMethodDecl>(ND)) 369 OS << "method "; 370 else if (isa<FunctionDecl>(ND)) 371 OS << "function "; 372 373 OS << '\''; 374 ND->getNameForDiagnostic(OS, Context.getPrintingPolicy(), true); 375 OS << '\''; 376 } 377 break; 378 } 379 case DiagnosticsEngine::ak_attr: { 380 const Attr *At = reinterpret_cast<Attr *>(Val); 381 assert(At && "Received null Attr object!"); 382 OS << '\'' << At->getSpelling() << '\''; 383 NeedQuotes = false; 384 break; 385 } 386 387 } 388 389 OS.flush(); 390 391 if (NeedQuotes) { 392 Output.insert(Output.begin()+OldEnd, '\''); 393 Output.push_back('\''); 394 } 395 } 396 397 /// TemplateDiff - A class that constructs a pretty string for a pair of 398 /// QualTypes. For the pair of types, a diff tree will be created containing 399 /// all the information about the templates and template arguments. Afterwards, 400 /// the tree is transformed to a string according to the options passed in. 401 namespace { 402 class TemplateDiff { 403 /// Context - The ASTContext which is used for comparing template arguments. 404 ASTContext &Context; 405 406 /// Policy - Used during expression printing. 407 PrintingPolicy Policy; 408 409 /// ElideType - Option to elide identical types. 410 bool ElideType; 411 412 /// PrintTree - Format output string as a tree. 413 bool PrintTree; 414 415 /// ShowColor - Diagnostics support color, so bolding will be used. 416 bool ShowColor; 417 418 /// FromType - When single type printing is selected, this is the type to be 419 /// be printed. When tree printing is selected, this type will show up first 420 /// in the tree. 421 QualType FromType; 422 423 /// ToType - The type that FromType is compared to. Only in tree printing 424 /// will this type be outputed. 425 QualType ToType; 426 427 /// OS - The stream used to construct the output strings. 428 raw_ostream &OS; 429 430 /// IsBold - Keeps track of the bold formatting for the output string. 431 bool IsBold; 432 433 /// DiffTree - A tree representation the differences between two types. 434 class DiffTree { 435 public: 436 /// DiffKind - The difference in a DiffNode and which fields are used. 437 enum DiffKind { 438 /// Incomplete or invalid node. 439 Invalid, 440 /// Another level of templates, uses TemplateDecl and Qualifiers 441 Template, 442 /// Type difference, uses QualType 443 Type, 444 /// Expression difference, uses Expr 445 Expression, 446 /// Template argument difference, uses TemplateDecl 447 TemplateTemplate, 448 /// Integer difference, uses APSInt and Expr 449 Integer, 450 /// Declaration difference, uses ValueDecl 451 Declaration 452 }; 453 private: 454 /// DiffNode - The root node stores the original type. Each child node 455 /// stores template arguments of their parents. For templated types, the 456 /// template decl is also stored. 457 struct DiffNode { 458 DiffKind Kind; 459 460 /// NextNode - The index of the next sibling node or 0. 461 unsigned NextNode; 462 463 /// ChildNode - The index of the first child node or 0. 464 unsigned ChildNode; 465 466 /// ParentNode - The index of the parent node. 467 unsigned ParentNode; 468 469 /// FromType, ToType - The type arguments. 470 QualType FromType, ToType; 471 472 /// FromExpr, ToExpr - The expression arguments. 473 Expr *FromExpr, *ToExpr; 474 475 /// FromTD, ToTD - The template decl for template template 476 /// arguments or the type arguments that are templates. 477 TemplateDecl *FromTD, *ToTD; 478 479 /// FromQual, ToQual - Qualifiers for template types. 480 Qualifiers FromQual, ToQual; 481 482 /// FromInt, ToInt - APSInt's for integral arguments. 483 llvm::APSInt FromInt, ToInt; 484 485 /// IsValidFromInt, IsValidToInt - Whether the APSInt's are valid. 486 bool IsValidFromInt, IsValidToInt; 487 488 /// FromValueDecl, ToValueDecl - Whether the argument is a decl. 489 ValueDecl *FromValueDecl, *ToValueDecl; 490 491 /// FromAddressOf, ToAddressOf - Whether the ValueDecl needs an address of 492 /// operator before it. 493 bool FromAddressOf, ToAddressOf; 494 495 /// FromDefault, ToDefault - Whether the argument is a default argument. 496 bool FromDefault, ToDefault; 497 498 /// Same - Whether the two arguments evaluate to the same value. 499 bool Same; 500 501 DiffNode(unsigned ParentNode = 0) 502 : Kind(Invalid), NextNode(0), ChildNode(0), ParentNode(ParentNode), 503 FromType(), ToType(), FromExpr(nullptr), ToExpr(nullptr), 504 FromTD(nullptr), ToTD(nullptr), IsValidFromInt(false), 505 IsValidToInt(false), FromValueDecl(nullptr), ToValueDecl(nullptr), 506 FromAddressOf(false), ToAddressOf(false), FromDefault(false), 507 ToDefault(false), Same(false) {} 508 }; 509 510 /// FlatTree - A flattened tree used to store the DiffNodes. 511 SmallVector<DiffNode, 16> FlatTree; 512 513 /// CurrentNode - The index of the current node being used. 514 unsigned CurrentNode; 515 516 /// NextFreeNode - The index of the next unused node. Used when creating 517 /// child nodes. 518 unsigned NextFreeNode; 519 520 /// ReadNode - The index of the current node being read. 521 unsigned ReadNode; 522 523 public: 524 DiffTree() : 525 CurrentNode(0), NextFreeNode(1) { 526 FlatTree.push_back(DiffNode()); 527 } 528 529 // Node writing functions. 530 /// SetNode - Sets FromTD and ToTD of the current node. 531 void SetNode(TemplateDecl *FromTD, TemplateDecl *ToTD) { 532 FlatTree[CurrentNode].FromTD = FromTD; 533 FlatTree[CurrentNode].ToTD = ToTD; 534 } 535 536 /// SetNode - Sets FromType and ToType of the current node. 537 void SetNode(QualType FromType, QualType ToType) { 538 FlatTree[CurrentNode].FromType = FromType; 539 FlatTree[CurrentNode].ToType = ToType; 540 } 541 542 /// SetNode - Set FromExpr and ToExpr of the current node. 543 void SetNode(Expr *FromExpr, Expr *ToExpr) { 544 FlatTree[CurrentNode].FromExpr = FromExpr; 545 FlatTree[CurrentNode].ToExpr = ToExpr; 546 } 547 548 /// SetNode - Set FromInt and ToInt of the current node. 549 void SetNode(llvm::APSInt FromInt, llvm::APSInt ToInt, 550 bool IsValidFromInt, bool IsValidToInt) { 551 FlatTree[CurrentNode].FromInt = FromInt; 552 FlatTree[CurrentNode].ToInt = ToInt; 553 FlatTree[CurrentNode].IsValidFromInt = IsValidFromInt; 554 FlatTree[CurrentNode].IsValidToInt = IsValidToInt; 555 } 556 557 /// SetNode - Set FromQual and ToQual of the current node. 558 void SetNode(Qualifiers FromQual, Qualifiers ToQual) { 559 FlatTree[CurrentNode].FromQual = FromQual; 560 FlatTree[CurrentNode].ToQual = ToQual; 561 } 562 563 /// SetNode - Set FromValueDecl and ToValueDecl of the current node. 564 void SetNode(ValueDecl *FromValueDecl, ValueDecl *ToValueDecl, 565 bool FromAddressOf, bool ToAddressOf) { 566 FlatTree[CurrentNode].FromValueDecl = FromValueDecl; 567 FlatTree[CurrentNode].ToValueDecl = ToValueDecl; 568 FlatTree[CurrentNode].FromAddressOf = FromAddressOf; 569 FlatTree[CurrentNode].ToAddressOf = ToAddressOf; 570 } 571 572 /// SetSame - Sets the same flag of the current node. 573 void SetSame(bool Same) { 574 FlatTree[CurrentNode].Same = Same; 575 } 576 577 /// SetDefault - Sets FromDefault and ToDefault flags of the current node. 578 void SetDefault(bool FromDefault, bool ToDefault) { 579 FlatTree[CurrentNode].FromDefault = FromDefault; 580 FlatTree[CurrentNode].ToDefault = ToDefault; 581 } 582 583 /// SetKind - Sets the current node's type. 584 void SetKind(DiffKind Kind) { 585 FlatTree[CurrentNode].Kind = Kind; 586 } 587 588 /// Up - Changes the node to the parent of the current node. 589 void Up() { 590 CurrentNode = FlatTree[CurrentNode].ParentNode; 591 } 592 593 /// AddNode - Adds a child node to the current node, then sets that node 594 /// node as the current node. 595 void AddNode() { 596 FlatTree.push_back(DiffNode(CurrentNode)); 597 DiffNode &Node = FlatTree[CurrentNode]; 598 if (Node.ChildNode == 0) { 599 // If a child node doesn't exist, add one. 600 Node.ChildNode = NextFreeNode; 601 } else { 602 // If a child node exists, find the last child node and add a 603 // next node to it. 604 unsigned i; 605 for (i = Node.ChildNode; FlatTree[i].NextNode != 0; 606 i = FlatTree[i].NextNode) { 607 } 608 FlatTree[i].NextNode = NextFreeNode; 609 } 610 CurrentNode = NextFreeNode; 611 ++NextFreeNode; 612 } 613 614 // Node reading functions. 615 /// StartTraverse - Prepares the tree for recursive traversal. 616 void StartTraverse() { 617 ReadNode = 0; 618 CurrentNode = NextFreeNode; 619 NextFreeNode = 0; 620 } 621 622 /// Parent - Move the current read node to its parent. 623 void Parent() { 624 ReadNode = FlatTree[ReadNode].ParentNode; 625 } 626 627 /// GetNode - Gets the FromType and ToType. 628 void GetNode(QualType &FromType, QualType &ToType) { 629 FromType = FlatTree[ReadNode].FromType; 630 ToType = FlatTree[ReadNode].ToType; 631 } 632 633 /// GetNode - Gets the FromExpr and ToExpr. 634 void GetNode(Expr *&FromExpr, Expr *&ToExpr) { 635 FromExpr = FlatTree[ReadNode].FromExpr; 636 ToExpr = FlatTree[ReadNode].ToExpr; 637 } 638 639 /// GetNode - Gets the FromTD and ToTD. 640 void GetNode(TemplateDecl *&FromTD, TemplateDecl *&ToTD) { 641 FromTD = FlatTree[ReadNode].FromTD; 642 ToTD = FlatTree[ReadNode].ToTD; 643 } 644 645 /// GetNode - Gets the FromInt and ToInt. 646 void GetNode(llvm::APSInt &FromInt, llvm::APSInt &ToInt, 647 bool &IsValidFromInt, bool &IsValidToInt) { 648 FromInt = FlatTree[ReadNode].FromInt; 649 ToInt = FlatTree[ReadNode].ToInt; 650 IsValidFromInt = FlatTree[ReadNode].IsValidFromInt; 651 IsValidToInt = FlatTree[ReadNode].IsValidToInt; 652 } 653 654 /// GetNode - Gets the FromQual and ToQual. 655 void GetNode(Qualifiers &FromQual, Qualifiers &ToQual) { 656 FromQual = FlatTree[ReadNode].FromQual; 657 ToQual = FlatTree[ReadNode].ToQual; 658 } 659 660 /// GetNode - Gets the FromValueDecl and ToValueDecl. 661 void GetNode(ValueDecl *&FromValueDecl, ValueDecl *&ToValueDecl, 662 bool &FromAddressOf, bool &ToAddressOf) { 663 FromValueDecl = FlatTree[ReadNode].FromValueDecl; 664 ToValueDecl = FlatTree[ReadNode].ToValueDecl; 665 FromAddressOf = FlatTree[ReadNode].FromAddressOf; 666 ToAddressOf = FlatTree[ReadNode].ToAddressOf; 667 } 668 669 /// NodeIsSame - Returns true the arguments are the same. 670 bool NodeIsSame() { 671 return FlatTree[ReadNode].Same; 672 } 673 674 /// HasChildrend - Returns true if the node has children. 675 bool HasChildren() { 676 return FlatTree[ReadNode].ChildNode != 0; 677 } 678 679 /// MoveToChild - Moves from the current node to its child. 680 void MoveToChild() { 681 ReadNode = FlatTree[ReadNode].ChildNode; 682 } 683 684 /// AdvanceSibling - If there is a next sibling, advance to it and return 685 /// true. Otherwise, return false. 686 bool AdvanceSibling() { 687 if (FlatTree[ReadNode].NextNode == 0) 688 return false; 689 690 ReadNode = FlatTree[ReadNode].NextNode; 691 return true; 692 } 693 694 /// HasNextSibling - Return true if the node has a next sibling. 695 bool HasNextSibling() { 696 return FlatTree[ReadNode].NextNode != 0; 697 } 698 699 /// FromDefault - Return true if the from argument is the default. 700 bool FromDefault() { 701 return FlatTree[ReadNode].FromDefault; 702 } 703 704 /// ToDefault - Return true if the to argument is the default. 705 bool ToDefault() { 706 return FlatTree[ReadNode].ToDefault; 707 } 708 709 /// Empty - Returns true if the tree has no information. 710 bool Empty() { 711 return GetKind() == Invalid; 712 } 713 714 /// GetKind - Returns the current node's type. 715 DiffKind GetKind() { 716 return FlatTree[ReadNode].Kind; 717 } 718 }; 719 720 DiffTree Tree; 721 722 /// TSTiterator - an iterator that is used to enter a 723 /// TemplateSpecializationType and read TemplateArguments inside template 724 /// parameter packs in order with the rest of the TemplateArguments. 725 struct TSTiterator { 726 typedef const TemplateArgument& reference; 727 typedef const TemplateArgument* pointer; 728 729 /// TST - the template specialization whose arguments this iterator 730 /// traverse over. 731 const TemplateSpecializationType *TST; 732 733 /// DesugarTST - desugared template specialization used to extract 734 /// default argument information 735 const TemplateSpecializationType *DesugarTST; 736 737 /// Index - the index of the template argument in TST. 738 unsigned Index; 739 740 /// CurrentTA - if CurrentTA is not the same as EndTA, then CurrentTA 741 /// points to a TemplateArgument within a parameter pack. 742 TemplateArgument::pack_iterator CurrentTA; 743 744 /// EndTA - the end iterator of a parameter pack 745 TemplateArgument::pack_iterator EndTA; 746 747 /// TSTiterator - Constructs an iterator and sets it to the first template 748 /// argument. 749 TSTiterator(ASTContext &Context, const TemplateSpecializationType *TST) 750 : TST(TST), 751 DesugarTST(GetTemplateSpecializationType(Context, TST->desugar())), 752 Index(0), CurrentTA(nullptr), EndTA(nullptr) { 753 if (isEnd()) return; 754 755 // Set to first template argument. If not a parameter pack, done. 756 TemplateArgument TA = TST->getArg(0); 757 if (TA.getKind() != TemplateArgument::Pack) return; 758 759 // Start looking into the parameter pack. 760 CurrentTA = TA.pack_begin(); 761 EndTA = TA.pack_end(); 762 763 // Found a valid template argument. 764 if (CurrentTA != EndTA) return; 765 766 // Parameter pack is empty, use the increment to get to a valid 767 // template argument. 768 ++(*this); 769 } 770 771 /// isEnd - Returns true if the iterator is one past the end. 772 bool isEnd() const { 773 return Index >= TST->getNumArgs(); 774 } 775 776 /// &operator++ - Increment the iterator to the next template argument. 777 TSTiterator &operator++() { 778 // After the end, Index should be the default argument position in 779 // DesugarTST, if it exists. 780 if (isEnd()) { 781 ++Index; 782 return *this; 783 } 784 785 // If in a parameter pack, advance in the parameter pack. 786 if (CurrentTA != EndTA) { 787 ++CurrentTA; 788 if (CurrentTA != EndTA) 789 return *this; 790 } 791 792 // Loop until a template argument is found, or the end is reached. 793 while (true) { 794 // Advance to the next template argument. Break if reached the end. 795 if (++Index == TST->getNumArgs()) break; 796 797 // If the TemplateArgument is not a parameter pack, done. 798 TemplateArgument TA = TST->getArg(Index); 799 if (TA.getKind() != TemplateArgument::Pack) break; 800 801 // Handle parameter packs. 802 CurrentTA = TA.pack_begin(); 803 EndTA = TA.pack_end(); 804 805 // If the parameter pack is empty, try to advance again. 806 if (CurrentTA != EndTA) break; 807 } 808 return *this; 809 } 810 811 /// operator* - Returns the appropriate TemplateArgument. 812 reference operator*() const { 813 assert(!isEnd() && "Index exceeds number of arguments."); 814 if (CurrentTA == EndTA) 815 return TST->getArg(Index); 816 else 817 return *CurrentTA; 818 } 819 820 /// operator-> - Allow access to the underlying TemplateArgument. 821 pointer operator->() const { 822 return &operator*(); 823 } 824 825 /// getDesugar - Returns the deduced template argument from DesguarTST 826 reference getDesugar() const { 827 return DesugarTST->getArg(Index); 828 } 829 }; 830 831 // These functions build up the template diff tree, including functions to 832 // retrieve and compare template arguments. 833 834 static const TemplateSpecializationType * GetTemplateSpecializationType( 835 ASTContext &Context, QualType Ty) { 836 if (const TemplateSpecializationType *TST = 837 Ty->getAs<TemplateSpecializationType>()) 838 return TST; 839 840 const RecordType *RT = Ty->getAs<RecordType>(); 841 842 if (!RT) 843 return nullptr; 844 845 const ClassTemplateSpecializationDecl *CTSD = 846 dyn_cast<ClassTemplateSpecializationDecl>(RT->getDecl()); 847 848 if (!CTSD) 849 return nullptr; 850 851 Ty = Context.getTemplateSpecializationType( 852 TemplateName(CTSD->getSpecializedTemplate()), 853 CTSD->getTemplateArgs().data(), 854 CTSD->getTemplateArgs().size(), 855 Ty.getLocalUnqualifiedType().getCanonicalType()); 856 857 return Ty->getAs<TemplateSpecializationType>(); 858 } 859 860 /// DiffTemplate - recursively visits template arguments and stores the 861 /// argument info into a tree. 862 void DiffTemplate(const TemplateSpecializationType *FromTST, 863 const TemplateSpecializationType *ToTST) { 864 // Begin descent into diffing template tree. 865 TemplateParameterList *ParamsFrom = 866 FromTST->getTemplateName().getAsTemplateDecl()->getTemplateParameters(); 867 TemplateParameterList *ParamsTo = 868 ToTST->getTemplateName().getAsTemplateDecl()->getTemplateParameters(); 869 unsigned TotalArgs = 0; 870 for (TSTiterator FromIter(Context, FromTST), ToIter(Context, ToTST); 871 !FromIter.isEnd() || !ToIter.isEnd(); ++TotalArgs) { 872 Tree.AddNode(); 873 874 // Get the parameter at index TotalArgs. If index is larger 875 // than the total number of parameters, then there is an 876 // argument pack, so re-use the last parameter. 877 unsigned ParamIndex = std::min(TotalArgs, ParamsFrom->size() - 1); 878 NamedDecl *ParamND = ParamsFrom->getParam(ParamIndex); 879 880 // Handle Types 881 if (TemplateTypeParmDecl *DefaultTTPD = 882 dyn_cast<TemplateTypeParmDecl>(ParamND)) { 883 QualType FromType, ToType; 884 FromType = GetType(FromIter, DefaultTTPD); 885 // A forward declaration can have no default arg but the actual class 886 // can, don't mix up iterators and get the original parameter. 887 ToType = GetType( 888 ToIter, cast<TemplateTypeParmDecl>(ParamsTo->getParam(ParamIndex))); 889 Tree.SetNode(FromType, ToType); 890 Tree.SetDefault(FromIter.isEnd() && !FromType.isNull(), 891 ToIter.isEnd() && !ToType.isNull()); 892 Tree.SetKind(DiffTree::Type); 893 if (!FromType.isNull() && !ToType.isNull()) { 894 if (Context.hasSameType(FromType, ToType)) { 895 Tree.SetSame(true); 896 } else { 897 Qualifiers FromQual = FromType.getQualifiers(), 898 ToQual = ToType.getQualifiers(); 899 const TemplateSpecializationType *FromArgTST = 900 GetTemplateSpecializationType(Context, FromType); 901 const TemplateSpecializationType *ToArgTST = 902 GetTemplateSpecializationType(Context, ToType); 903 904 if (FromArgTST && ToArgTST && 905 hasSameTemplate(FromArgTST, ToArgTST)) { 906 FromQual -= QualType(FromArgTST, 0).getQualifiers(); 907 ToQual -= QualType(ToArgTST, 0).getQualifiers(); 908 Tree.SetNode(FromArgTST->getTemplateName().getAsTemplateDecl(), 909 ToArgTST->getTemplateName().getAsTemplateDecl()); 910 Tree.SetNode(FromQual, ToQual); 911 Tree.SetKind(DiffTree::Template); 912 DiffTemplate(FromArgTST, ToArgTST); 913 } 914 } 915 } 916 } 917 918 // Handle Expressions 919 if (NonTypeTemplateParmDecl *DefaultNTTPD = 920 dyn_cast<NonTypeTemplateParmDecl>(ParamND)) { 921 Expr *FromExpr = nullptr, *ToExpr = nullptr; 922 llvm::APSInt FromInt, ToInt; 923 ValueDecl *FromValueDecl = nullptr, *ToValueDecl = nullptr; 924 unsigned ParamWidth = 128; // Safe default 925 if (DefaultNTTPD->getType()->isIntegralOrEnumerationType()) 926 ParamWidth = Context.getIntWidth(DefaultNTTPD->getType()); 927 bool HasFromInt = !FromIter.isEnd() && 928 FromIter->getKind() == TemplateArgument::Integral; 929 bool HasToInt = !ToIter.isEnd() && 930 ToIter->getKind() == TemplateArgument::Integral; 931 bool HasFromValueDecl = 932 !FromIter.isEnd() && 933 FromIter->getKind() == TemplateArgument::Declaration; 934 bool HasToValueDecl = 935 !ToIter.isEnd() && 936 ToIter->getKind() == TemplateArgument::Declaration; 937 938 assert(((!HasFromInt && !HasToInt) || 939 (!HasFromValueDecl && !HasToValueDecl)) && 940 "Template argument cannot be both integer and declaration"); 941 942 if (HasFromInt) 943 FromInt = FromIter->getAsIntegral(); 944 else if (HasFromValueDecl) 945 FromValueDecl = FromIter->getAsDecl(); 946 else 947 FromExpr = GetExpr(FromIter, DefaultNTTPD); 948 949 if (HasToInt) 950 ToInt = ToIter->getAsIntegral(); 951 else if (HasToValueDecl) 952 ToValueDecl = ToIter->getAsDecl(); 953 else 954 ToExpr = GetExpr(ToIter, DefaultNTTPD); 955 956 if (!HasFromInt && !HasToInt && !HasFromValueDecl && !HasToValueDecl) { 957 Tree.SetNode(FromExpr, ToExpr); 958 Tree.SetDefault(FromIter.isEnd() && FromExpr, 959 ToIter.isEnd() && ToExpr); 960 if (DefaultNTTPD->getType()->isIntegralOrEnumerationType()) { 961 if (FromExpr) 962 HasFromInt = GetInt(FromIter, FromExpr, FromInt); 963 if (ToExpr) 964 HasToInt = GetInt(ToIter, ToExpr, ToInt); 965 } 966 if (HasFromInt && HasToInt) { 967 Tree.SetNode(FromInt, ToInt, HasFromInt, HasToInt); 968 Tree.SetSame(IsSameConvertedInt(ParamWidth, FromInt, ToInt)); 969 Tree.SetKind(DiffTree::Integer); 970 } else if (HasFromInt || HasToInt) { 971 Tree.SetNode(FromInt, ToInt, HasFromInt, HasToInt); 972 Tree.SetSame(false); 973 Tree.SetKind(DiffTree::Integer); 974 } else { 975 Tree.SetSame(IsEqualExpr(Context, ParamWidth, FromExpr, ToExpr)); 976 Tree.SetKind(DiffTree::Expression); 977 } 978 } else if (HasFromInt || HasToInt) { 979 if (!HasFromInt && FromExpr) 980 HasFromInt = GetInt(FromIter, FromExpr, FromInt); 981 if (!HasToInt && ToExpr) 982 HasToInt = GetInt(ToIter, ToExpr, ToInt); 983 Tree.SetNode(FromInt, ToInt, HasFromInt, HasToInt); 984 Tree.SetSame(IsSameConvertedInt(ParamWidth, FromInt, ToInt)); 985 Tree.SetDefault(FromIter.isEnd() && HasFromInt, 986 ToIter.isEnd() && HasToInt); 987 Tree.SetKind(DiffTree::Integer); 988 } else { 989 if (!HasFromValueDecl && FromExpr) 990 FromValueDecl = GetValueDecl(FromIter, FromExpr); 991 if (!HasToValueDecl && ToExpr) 992 ToValueDecl = GetValueDecl(ToIter, ToExpr); 993 QualType ArgumentType = DefaultNTTPD->getType(); 994 bool FromAddressOf = FromValueDecl && 995 !ArgumentType->isReferenceType() && 996 !FromValueDecl->getType()->isArrayType(); 997 bool ToAddressOf = ToValueDecl && 998 !ArgumentType->isReferenceType() && 999 !ToValueDecl->getType()->isArrayType(); 1000 Tree.SetNode(FromValueDecl, ToValueDecl, FromAddressOf, ToAddressOf); 1001 Tree.SetSame(FromValueDecl && ToValueDecl && 1002 FromValueDecl->getCanonicalDecl() == 1003 ToValueDecl->getCanonicalDecl()); 1004 Tree.SetDefault(FromIter.isEnd() && FromValueDecl, 1005 ToIter.isEnd() && ToValueDecl); 1006 Tree.SetKind(DiffTree::Declaration); 1007 } 1008 } 1009 1010 // Handle Templates 1011 if (TemplateTemplateParmDecl *DefaultTTPD = 1012 dyn_cast<TemplateTemplateParmDecl>(ParamND)) { 1013 TemplateDecl *FromDecl, *ToDecl; 1014 FromDecl = GetTemplateDecl(FromIter, DefaultTTPD); 1015 ToDecl = GetTemplateDecl(ToIter, DefaultTTPD); 1016 Tree.SetNode(FromDecl, ToDecl); 1017 Tree.SetSame( 1018 FromDecl && ToDecl && 1019 FromDecl->getCanonicalDecl() == ToDecl->getCanonicalDecl()); 1020 Tree.SetKind(DiffTree::TemplateTemplate); 1021 } 1022 1023 ++FromIter; 1024 ++ToIter; 1025 Tree.Up(); 1026 } 1027 } 1028 1029 /// makeTemplateList - Dump every template alias into the vector. 1030 static void makeTemplateList( 1031 SmallVectorImpl<const TemplateSpecializationType *> &TemplateList, 1032 const TemplateSpecializationType *TST) { 1033 while (TST) { 1034 TemplateList.push_back(TST); 1035 if (!TST->isTypeAlias()) 1036 return; 1037 TST = TST->getAliasedType()->getAs<TemplateSpecializationType>(); 1038 } 1039 } 1040 1041 /// hasSameBaseTemplate - Returns true when the base templates are the same, 1042 /// even if the template arguments are not. 1043 static bool hasSameBaseTemplate(const TemplateSpecializationType *FromTST, 1044 const TemplateSpecializationType *ToTST) { 1045 return FromTST->getTemplateName().getAsTemplateDecl()->getCanonicalDecl() == 1046 ToTST->getTemplateName().getAsTemplateDecl()->getCanonicalDecl(); 1047 } 1048 1049 /// hasSameTemplate - Returns true if both types are specialized from the 1050 /// same template declaration. If they come from different template aliases, 1051 /// do a parallel ascension search to determine the highest template alias in 1052 /// common and set the arguments to them. 1053 static bool hasSameTemplate(const TemplateSpecializationType *&FromTST, 1054 const TemplateSpecializationType *&ToTST) { 1055 // Check the top templates if they are the same. 1056 if (hasSameBaseTemplate(FromTST, ToTST)) 1057 return true; 1058 1059 // Create vectors of template aliases. 1060 SmallVector<const TemplateSpecializationType*, 1> FromTemplateList, 1061 ToTemplateList; 1062 1063 makeTemplateList(FromTemplateList, FromTST); 1064 makeTemplateList(ToTemplateList, ToTST); 1065 1066 SmallVectorImpl<const TemplateSpecializationType *>::reverse_iterator 1067 FromIter = FromTemplateList.rbegin(), FromEnd = FromTemplateList.rend(), 1068 ToIter = ToTemplateList.rbegin(), ToEnd = ToTemplateList.rend(); 1069 1070 // Check if the lowest template types are the same. If not, return. 1071 if (!hasSameBaseTemplate(*FromIter, *ToIter)) 1072 return false; 1073 1074 // Begin searching up the template aliases. The bottom most template 1075 // matches so move up until one pair does not match. Use the template 1076 // right before that one. 1077 for (; FromIter != FromEnd && ToIter != ToEnd; ++FromIter, ++ToIter) { 1078 if (!hasSameBaseTemplate(*FromIter, *ToIter)) 1079 break; 1080 } 1081 1082 FromTST = FromIter[-1]; 1083 ToTST = ToIter[-1]; 1084 1085 return true; 1086 } 1087 1088 /// GetType - Retrieves the template type arguments, including default 1089 /// arguments. 1090 QualType GetType(const TSTiterator &Iter, TemplateTypeParmDecl *DefaultTTPD) { 1091 bool isVariadic = DefaultTTPD->isParameterPack(); 1092 1093 if (!Iter.isEnd()) 1094 return Iter->getAsType(); 1095 if (isVariadic) 1096 return QualType(); 1097 1098 QualType ArgType = DefaultTTPD->getDefaultArgument(); 1099 if (ArgType->isDependentType()) 1100 return Iter.getDesugar().getAsType(); 1101 1102 return ArgType; 1103 } 1104 1105 /// GetExpr - Retrieves the template expression argument, including default 1106 /// arguments. 1107 Expr *GetExpr(const TSTiterator &Iter, NonTypeTemplateParmDecl *DefaultNTTPD) { 1108 Expr *ArgExpr = nullptr; 1109 bool isVariadic = DefaultNTTPD->isParameterPack(); 1110 1111 if (!Iter.isEnd()) 1112 ArgExpr = Iter->getAsExpr(); 1113 else if (!isVariadic) 1114 ArgExpr = DefaultNTTPD->getDefaultArgument(); 1115 1116 if (ArgExpr) 1117 while (SubstNonTypeTemplateParmExpr *SNTTPE = 1118 dyn_cast<SubstNonTypeTemplateParmExpr>(ArgExpr)) 1119 ArgExpr = SNTTPE->getReplacement(); 1120 1121 return ArgExpr; 1122 } 1123 1124 /// GetInt - Retrieves the template integer argument, including evaluating 1125 /// default arguments. 1126 bool GetInt(const TSTiterator &Iter, Expr *ArgExpr, llvm::APInt &Int) { 1127 // Default, value-depenedent expressions require fetching 1128 // from the desugared TemplateArgument, otherwise expression needs to 1129 // be evaluatable. 1130 if (Iter.isEnd() && ArgExpr->isValueDependent()) { 1131 switch (Iter.getDesugar().getKind()) { 1132 case TemplateArgument::Integral: 1133 Int = Iter.getDesugar().getAsIntegral(); 1134 return true; 1135 case TemplateArgument::Expression: 1136 ArgExpr = Iter.getDesugar().getAsExpr(); 1137 Int = ArgExpr->EvaluateKnownConstInt(Context); 1138 return true; 1139 default: 1140 llvm_unreachable("Unexpected template argument kind"); 1141 } 1142 } else if (ArgExpr->isEvaluatable(Context)) { 1143 Int = ArgExpr->EvaluateKnownConstInt(Context); 1144 return true; 1145 } 1146 1147 return false; 1148 } 1149 1150 /// GetValueDecl - Retrieves the template Decl argument, including 1151 /// default expression argument. 1152 ValueDecl *GetValueDecl(const TSTiterator &Iter, Expr *ArgExpr) { 1153 // Default, value-depenedent expressions require fetching 1154 // from the desugared TemplateArgument 1155 if (Iter.isEnd() && ArgExpr->isValueDependent()) 1156 switch (Iter.getDesugar().getKind()) { 1157 case TemplateArgument::Declaration: 1158 return Iter.getDesugar().getAsDecl(); 1159 case TemplateArgument::Expression: 1160 ArgExpr = Iter.getDesugar().getAsExpr(); 1161 return cast<DeclRefExpr>(ArgExpr)->getDecl(); 1162 default: 1163 llvm_unreachable("Unexpected template argument kind"); 1164 } 1165 DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(ArgExpr); 1166 if (!DRE) { 1167 DRE = cast<DeclRefExpr>(cast<UnaryOperator>(ArgExpr)->getSubExpr()); 1168 } 1169 1170 return DRE->getDecl(); 1171 } 1172 1173 /// GetTemplateDecl - Retrieves the template template arguments, including 1174 /// default arguments. 1175 TemplateDecl *GetTemplateDecl(const TSTiterator &Iter, 1176 TemplateTemplateParmDecl *DefaultTTPD) { 1177 bool isVariadic = DefaultTTPD->isParameterPack(); 1178 1179 TemplateArgument TA = DefaultTTPD->getDefaultArgument().getArgument(); 1180 TemplateDecl *DefaultTD = nullptr; 1181 if (TA.getKind() != TemplateArgument::Null) 1182 DefaultTD = TA.getAsTemplate().getAsTemplateDecl(); 1183 1184 if (!Iter.isEnd()) 1185 return Iter->getAsTemplate().getAsTemplateDecl(); 1186 if (!isVariadic) 1187 return DefaultTD; 1188 1189 return nullptr; 1190 } 1191 1192 /// IsSameConvertedInt - Returns true if both integers are equal when 1193 /// converted to an integer type with the given width. 1194 static bool IsSameConvertedInt(unsigned Width, const llvm::APSInt &X, 1195 const llvm::APSInt &Y) { 1196 llvm::APInt ConvertedX = X.extOrTrunc(Width); 1197 llvm::APInt ConvertedY = Y.extOrTrunc(Width); 1198 return ConvertedX == ConvertedY; 1199 } 1200 1201 /// IsEqualExpr - Returns true if the expressions evaluate to the same value. 1202 static bool IsEqualExpr(ASTContext &Context, unsigned ParamWidth, 1203 Expr *FromExpr, Expr *ToExpr) { 1204 if (FromExpr == ToExpr) 1205 return true; 1206 1207 if (!FromExpr || !ToExpr) 1208 return false; 1209 1210 FromExpr = FromExpr->IgnoreParens(); 1211 ToExpr = ToExpr->IgnoreParens(); 1212 1213 DeclRefExpr *FromDRE = dyn_cast<DeclRefExpr>(FromExpr), 1214 *ToDRE = dyn_cast<DeclRefExpr>(ToExpr); 1215 1216 if (FromDRE || ToDRE) { 1217 if (!FromDRE || !ToDRE) 1218 return false; 1219 return FromDRE->getDecl() == ToDRE->getDecl(); 1220 } 1221 1222 Expr::EvalResult FromResult, ToResult; 1223 if (!FromExpr->EvaluateAsRValue(FromResult, Context) || 1224 !ToExpr->EvaluateAsRValue(ToResult, Context)) 1225 return false; 1226 1227 APValue &FromVal = FromResult.Val; 1228 APValue &ToVal = ToResult.Val; 1229 1230 if (FromVal.getKind() != ToVal.getKind()) return false; 1231 1232 switch (FromVal.getKind()) { 1233 case APValue::Int: 1234 return IsSameConvertedInt(ParamWidth, FromVal.getInt(), ToVal.getInt()); 1235 case APValue::LValue: { 1236 APValue::LValueBase FromBase = FromVal.getLValueBase(); 1237 APValue::LValueBase ToBase = ToVal.getLValueBase(); 1238 if (FromBase.isNull() && ToBase.isNull()) 1239 return true; 1240 if (FromBase.isNull() || ToBase.isNull()) 1241 return false; 1242 return FromBase.get<const ValueDecl*>() == 1243 ToBase.get<const ValueDecl*>(); 1244 } 1245 case APValue::MemberPointer: 1246 return FromVal.getMemberPointerDecl() == ToVal.getMemberPointerDecl(); 1247 default: 1248 llvm_unreachable("Unknown template argument expression."); 1249 } 1250 } 1251 1252 // These functions converts the tree representation of the template 1253 // differences into the internal character vector. 1254 1255 /// TreeToString - Converts the Tree object into a character stream which 1256 /// will later be turned into the output string. 1257 void TreeToString(int Indent = 1) { 1258 if (PrintTree) { 1259 OS << '\n'; 1260 OS.indent(2 * Indent); 1261 ++Indent; 1262 } 1263 1264 // Handle cases where the difference is not templates with different 1265 // arguments. 1266 switch (Tree.GetKind()) { 1267 case DiffTree::Invalid: 1268 llvm_unreachable("Template diffing failed with bad DiffNode"); 1269 case DiffTree::Type: { 1270 QualType FromType, ToType; 1271 Tree.GetNode(FromType, ToType); 1272 PrintTypeNames(FromType, ToType, Tree.FromDefault(), Tree.ToDefault(), 1273 Tree.NodeIsSame()); 1274 return; 1275 } 1276 case DiffTree::Expression: { 1277 Expr *FromExpr, *ToExpr; 1278 Tree.GetNode(FromExpr, ToExpr); 1279 PrintExpr(FromExpr, ToExpr, Tree.FromDefault(), Tree.ToDefault(), 1280 Tree.NodeIsSame()); 1281 return; 1282 } 1283 case DiffTree::TemplateTemplate: { 1284 TemplateDecl *FromTD, *ToTD; 1285 Tree.GetNode(FromTD, ToTD); 1286 PrintTemplateTemplate(FromTD, ToTD, Tree.FromDefault(), 1287 Tree.ToDefault(), Tree.NodeIsSame()); 1288 return; 1289 } 1290 case DiffTree::Integer: { 1291 llvm::APSInt FromInt, ToInt; 1292 Expr *FromExpr, *ToExpr; 1293 bool IsValidFromInt, IsValidToInt; 1294 Tree.GetNode(FromExpr, ToExpr); 1295 Tree.GetNode(FromInt, ToInt, IsValidFromInt, IsValidToInt); 1296 PrintAPSInt(FromInt, ToInt, IsValidFromInt, IsValidToInt, 1297 FromExpr, ToExpr, Tree.FromDefault(), Tree.ToDefault(), 1298 Tree.NodeIsSame()); 1299 return; 1300 } 1301 case DiffTree::Declaration: { 1302 ValueDecl *FromValueDecl, *ToValueDecl; 1303 bool FromAddressOf, ToAddressOf; 1304 Tree.GetNode(FromValueDecl, ToValueDecl, FromAddressOf, ToAddressOf); 1305 PrintValueDecl(FromValueDecl, ToValueDecl, FromAddressOf, ToAddressOf, 1306 Tree.FromDefault(), Tree.ToDefault(), Tree.NodeIsSame()); 1307 return; 1308 } 1309 case DiffTree::Template: { 1310 // Node is root of template. Recurse on children. 1311 TemplateDecl *FromTD, *ToTD; 1312 Tree.GetNode(FromTD, ToTD); 1313 1314 if (!Tree.HasChildren()) { 1315 // If we're dealing with a template specialization with zero 1316 // arguments, there are no children; special-case this. 1317 OS << FromTD->getNameAsString() << "<>"; 1318 return; 1319 } 1320 1321 Qualifiers FromQual, ToQual; 1322 Tree.GetNode(FromQual, ToQual); 1323 PrintQualifiers(FromQual, ToQual); 1324 1325 OS << FromTD->getNameAsString() << '<'; 1326 Tree.MoveToChild(); 1327 unsigned NumElideArgs = 0; 1328 do { 1329 if (ElideType) { 1330 if (Tree.NodeIsSame()) { 1331 ++NumElideArgs; 1332 continue; 1333 } 1334 if (NumElideArgs > 0) { 1335 PrintElideArgs(NumElideArgs, Indent); 1336 NumElideArgs = 0; 1337 OS << ", "; 1338 } 1339 } 1340 TreeToString(Indent); 1341 if (Tree.HasNextSibling()) 1342 OS << ", "; 1343 } while (Tree.AdvanceSibling()); 1344 if (NumElideArgs > 0) 1345 PrintElideArgs(NumElideArgs, Indent); 1346 1347 Tree.Parent(); 1348 OS << ">"; 1349 return; 1350 } 1351 } 1352 } 1353 1354 // To signal to the text printer that a certain text needs to be bolded, 1355 // a special character is injected into the character stream which the 1356 // text printer will later strip out. 1357 1358 /// Bold - Start bolding text. 1359 void Bold() { 1360 assert(!IsBold && "Attempting to bold text that is already bold."); 1361 IsBold = true; 1362 if (ShowColor) 1363 OS << ToggleHighlight; 1364 } 1365 1366 /// Unbold - Stop bolding text. 1367 void Unbold() { 1368 assert(IsBold && "Attempting to remove bold from unbold text."); 1369 IsBold = false; 1370 if (ShowColor) 1371 OS << ToggleHighlight; 1372 } 1373 1374 // Functions to print out the arguments and highlighting the difference. 1375 1376 /// PrintTypeNames - prints the typenames, bolding differences. Will detect 1377 /// typenames that are the same and attempt to disambiguate them by using 1378 /// canonical typenames. 1379 void PrintTypeNames(QualType FromType, QualType ToType, 1380 bool FromDefault, bool ToDefault, bool Same) { 1381 assert((!FromType.isNull() || !ToType.isNull()) && 1382 "Only one template argument may be missing."); 1383 1384 if (Same) { 1385 OS << FromType.getAsString(); 1386 return; 1387 } 1388 1389 if (!FromType.isNull() && !ToType.isNull() && 1390 FromType.getLocalUnqualifiedType() == 1391 ToType.getLocalUnqualifiedType()) { 1392 Qualifiers FromQual = FromType.getLocalQualifiers(), 1393 ToQual = ToType.getLocalQualifiers(); 1394 PrintQualifiers(FromQual, ToQual); 1395 FromType.getLocalUnqualifiedType().print(OS, Policy); 1396 return; 1397 } 1398 1399 std::string FromTypeStr = FromType.isNull() ? "(no argument)" 1400 : FromType.getAsString(); 1401 std::string ToTypeStr = ToType.isNull() ? "(no argument)" 1402 : ToType.getAsString(); 1403 // Switch to canonical typename if it is better. 1404 // TODO: merge this with other aka printing above. 1405 if (FromTypeStr == ToTypeStr) { 1406 std::string FromCanTypeStr = FromType.getCanonicalType().getAsString(); 1407 std::string ToCanTypeStr = ToType.getCanonicalType().getAsString(); 1408 if (FromCanTypeStr != ToCanTypeStr) { 1409 FromTypeStr = FromCanTypeStr; 1410 ToTypeStr = ToCanTypeStr; 1411 } 1412 } 1413 1414 if (PrintTree) OS << '['; 1415 OS << (FromDefault ? "(default) " : ""); 1416 Bold(); 1417 OS << FromTypeStr; 1418 Unbold(); 1419 if (PrintTree) { 1420 OS << " != " << (ToDefault ? "(default) " : ""); 1421 Bold(); 1422 OS << ToTypeStr; 1423 Unbold(); 1424 OS << "]"; 1425 } 1426 return; 1427 } 1428 1429 /// PrintExpr - Prints out the expr template arguments, highlighting argument 1430 /// differences. 1431 void PrintExpr(const Expr *FromExpr, const Expr *ToExpr, 1432 bool FromDefault, bool ToDefault, bool Same) { 1433 assert((FromExpr || ToExpr) && 1434 "Only one template argument may be missing."); 1435 if (Same) { 1436 PrintExpr(FromExpr); 1437 } else if (!PrintTree) { 1438 OS << (FromDefault ? "(default) " : ""); 1439 Bold(); 1440 PrintExpr(FromExpr); 1441 Unbold(); 1442 } else { 1443 OS << (FromDefault ? "[(default) " : "["); 1444 Bold(); 1445 PrintExpr(FromExpr); 1446 Unbold(); 1447 OS << " != " << (ToDefault ? "(default) " : ""); 1448 Bold(); 1449 PrintExpr(ToExpr); 1450 Unbold(); 1451 OS << ']'; 1452 } 1453 } 1454 1455 /// PrintExpr - Actual formatting and printing of expressions. 1456 void PrintExpr(const Expr *E) { 1457 if (!E) 1458 OS << "(no argument)"; 1459 else 1460 E->printPretty(OS, nullptr, Policy); 1461 } 1462 1463 /// PrintTemplateTemplate - Handles printing of template template arguments, 1464 /// highlighting argument differences. 1465 void PrintTemplateTemplate(TemplateDecl *FromTD, TemplateDecl *ToTD, 1466 bool FromDefault, bool ToDefault, bool Same) { 1467 assert((FromTD || ToTD) && "Only one template argument may be missing."); 1468 1469 std::string FromName = FromTD ? FromTD->getName() : "(no argument)"; 1470 std::string ToName = ToTD ? ToTD->getName() : "(no argument)"; 1471 if (FromTD && ToTD && FromName == ToName) { 1472 FromName = FromTD->getQualifiedNameAsString(); 1473 ToName = ToTD->getQualifiedNameAsString(); 1474 } 1475 1476 if (Same) { 1477 OS << "template " << FromTD->getNameAsString(); 1478 } else if (!PrintTree) { 1479 OS << (FromDefault ? "(default) template " : "template "); 1480 Bold(); 1481 OS << FromName; 1482 Unbold(); 1483 } else { 1484 OS << (FromDefault ? "[(default) template " : "[template "); 1485 Bold(); 1486 OS << FromName; 1487 Unbold(); 1488 OS << " != " << (ToDefault ? "(default) template " : "template "); 1489 Bold(); 1490 OS << ToName; 1491 Unbold(); 1492 OS << ']'; 1493 } 1494 } 1495 1496 /// PrintAPSInt - Handles printing of integral arguments, highlighting 1497 /// argument differences. 1498 void PrintAPSInt(llvm::APSInt FromInt, llvm::APSInt ToInt, 1499 bool IsValidFromInt, bool IsValidToInt, Expr *FromExpr, 1500 Expr *ToExpr, bool FromDefault, bool ToDefault, bool Same) { 1501 assert((IsValidFromInt || IsValidToInt) && 1502 "Only one integral argument may be missing."); 1503 1504 if (Same) { 1505 OS << FromInt.toString(10); 1506 } else if (!PrintTree) { 1507 OS << (FromDefault ? "(default) " : ""); 1508 PrintAPSInt(FromInt, FromExpr, IsValidFromInt); 1509 } else { 1510 OS << (FromDefault ? "[(default) " : "["); 1511 PrintAPSInt(FromInt, FromExpr, IsValidFromInt); 1512 OS << " != " << (ToDefault ? "(default) " : ""); 1513 PrintAPSInt(ToInt, ToExpr, IsValidToInt); 1514 OS << ']'; 1515 } 1516 } 1517 1518 /// PrintAPSInt - If valid, print the APSInt. If the expression is 1519 /// gives more information, print it too. 1520 void PrintAPSInt(llvm::APSInt Val, Expr *E, bool Valid) { 1521 Bold(); 1522 if (Valid) { 1523 if (HasExtraInfo(E)) { 1524 PrintExpr(E); 1525 Unbold(); 1526 OS << " aka "; 1527 Bold(); 1528 } 1529 OS << Val.toString(10); 1530 } else if (E) { 1531 PrintExpr(E); 1532 } else { 1533 OS << "(no argument)"; 1534 } 1535 Unbold(); 1536 } 1537 1538 /// HasExtraInfo - Returns true if E is not an integer literal or the 1539 /// negation of an integer literal 1540 bool HasExtraInfo(Expr *E) { 1541 if (!E) return false; 1542 if (isa<IntegerLiteral>(E)) return false; 1543 1544 if (UnaryOperator *UO = dyn_cast<UnaryOperator>(E)) 1545 if (UO->getOpcode() == UO_Minus) 1546 if (isa<IntegerLiteral>(UO->getSubExpr())) 1547 return false; 1548 1549 return true; 1550 } 1551 1552 /// PrintDecl - Handles printing of Decl arguments, highlighting 1553 /// argument differences. 1554 void PrintValueDecl(ValueDecl *FromValueDecl, ValueDecl *ToValueDecl, 1555 bool FromAddressOf, bool ToAddressOf, bool FromDefault, 1556 bool ToDefault, bool Same) { 1557 assert((FromValueDecl || ToValueDecl) && 1558 "Only one Decl argument may be NULL"); 1559 1560 if (Same) { 1561 OS << FromValueDecl->getName(); 1562 } else if (!PrintTree) { 1563 OS << (FromDefault ? "(default) " : ""); 1564 Bold(); 1565 if (FromAddressOf) 1566 OS << "&"; 1567 OS << (FromValueDecl ? FromValueDecl->getName() : "(no argument)"); 1568 Unbold(); 1569 } else { 1570 OS << (FromDefault ? "[(default) " : "["); 1571 Bold(); 1572 if (FromAddressOf) 1573 OS << "&"; 1574 OS << (FromValueDecl ? FromValueDecl->getName() : "(no argument)"); 1575 Unbold(); 1576 OS << " != " << (ToDefault ? "(default) " : ""); 1577 Bold(); 1578 if (ToAddressOf) 1579 OS << "&"; 1580 OS << (ToValueDecl ? ToValueDecl->getName() : "(no argument)"); 1581 Unbold(); 1582 OS << ']'; 1583 } 1584 1585 } 1586 1587 // Prints the appropriate placeholder for elided template arguments. 1588 void PrintElideArgs(unsigned NumElideArgs, unsigned Indent) { 1589 if (PrintTree) { 1590 OS << '\n'; 1591 for (unsigned i = 0; i < Indent; ++i) 1592 OS << " "; 1593 } 1594 if (NumElideArgs == 0) return; 1595 if (NumElideArgs == 1) 1596 OS << "[...]"; 1597 else 1598 OS << "[" << NumElideArgs << " * ...]"; 1599 } 1600 1601 // Prints and highlights differences in Qualifiers. 1602 void PrintQualifiers(Qualifiers FromQual, Qualifiers ToQual) { 1603 // Both types have no qualifiers 1604 if (FromQual.empty() && ToQual.empty()) 1605 return; 1606 1607 // Both types have same qualifiers 1608 if (FromQual == ToQual) { 1609 PrintQualifier(FromQual, /*ApplyBold*/false); 1610 return; 1611 } 1612 1613 // Find common qualifiers and strip them from FromQual and ToQual. 1614 Qualifiers CommonQual = Qualifiers::removeCommonQualifiers(FromQual, 1615 ToQual); 1616 1617 // The qualifiers are printed before the template name. 1618 // Inline printing: 1619 // The common qualifiers are printed. Then, qualifiers only in this type 1620 // are printed and highlighted. Finally, qualifiers only in the other 1621 // type are printed and highlighted inside parentheses after "missing". 1622 // Tree printing: 1623 // Qualifiers are printed next to each other, inside brackets, and 1624 // separated by "!=". The printing order is: 1625 // common qualifiers, highlighted from qualifiers, "!=", 1626 // common qualifiers, highlighted to qualifiers 1627 if (PrintTree) { 1628 OS << "["; 1629 if (CommonQual.empty() && FromQual.empty()) { 1630 Bold(); 1631 OS << "(no qualifiers) "; 1632 Unbold(); 1633 } else { 1634 PrintQualifier(CommonQual, /*ApplyBold*/false); 1635 PrintQualifier(FromQual, /*ApplyBold*/true); 1636 } 1637 OS << "!= "; 1638 if (CommonQual.empty() && ToQual.empty()) { 1639 Bold(); 1640 OS << "(no qualifiers)"; 1641 Unbold(); 1642 } else { 1643 PrintQualifier(CommonQual, /*ApplyBold*/false, 1644 /*appendSpaceIfNonEmpty*/!ToQual.empty()); 1645 PrintQualifier(ToQual, /*ApplyBold*/true, 1646 /*appendSpaceIfNonEmpty*/false); 1647 } 1648 OS << "] "; 1649 } else { 1650 PrintQualifier(CommonQual, /*ApplyBold*/false); 1651 PrintQualifier(FromQual, /*ApplyBold*/true); 1652 } 1653 } 1654 1655 void PrintQualifier(Qualifiers Q, bool ApplyBold, 1656 bool AppendSpaceIfNonEmpty = true) { 1657 if (Q.empty()) return; 1658 if (ApplyBold) Bold(); 1659 Q.print(OS, Policy, AppendSpaceIfNonEmpty); 1660 if (ApplyBold) Unbold(); 1661 } 1662 1663 public: 1664 1665 TemplateDiff(raw_ostream &OS, ASTContext &Context, QualType FromType, 1666 QualType ToType, bool PrintTree, bool PrintFromType, 1667 bool ElideType, bool ShowColor) 1668 : Context(Context), 1669 Policy(Context.getLangOpts()), 1670 ElideType(ElideType), 1671 PrintTree(PrintTree), 1672 ShowColor(ShowColor), 1673 // When printing a single type, the FromType is the one printed. 1674 FromType(PrintFromType ? FromType : ToType), 1675 ToType(PrintFromType ? ToType : FromType), 1676 OS(OS), 1677 IsBold(false) { 1678 } 1679 1680 /// DiffTemplate - Start the template type diffing. 1681 void DiffTemplate() { 1682 Qualifiers FromQual = FromType.getQualifiers(), 1683 ToQual = ToType.getQualifiers(); 1684 1685 const TemplateSpecializationType *FromOrigTST = 1686 GetTemplateSpecializationType(Context, FromType); 1687 const TemplateSpecializationType *ToOrigTST = 1688 GetTemplateSpecializationType(Context, ToType); 1689 1690 // Only checking templates. 1691 if (!FromOrigTST || !ToOrigTST) 1692 return; 1693 1694 // Different base templates. 1695 if (!hasSameTemplate(FromOrigTST, ToOrigTST)) { 1696 return; 1697 } 1698 1699 FromQual -= QualType(FromOrigTST, 0).getQualifiers(); 1700 ToQual -= QualType(ToOrigTST, 0).getQualifiers(); 1701 Tree.SetNode(FromType, ToType); 1702 Tree.SetNode(FromQual, ToQual); 1703 Tree.SetKind(DiffTree::Template); 1704 1705 // Same base template, but different arguments. 1706 Tree.SetNode(FromOrigTST->getTemplateName().getAsTemplateDecl(), 1707 ToOrigTST->getTemplateName().getAsTemplateDecl()); 1708 1709 DiffTemplate(FromOrigTST, ToOrigTST); 1710 } 1711 1712 /// Emit - When the two types given are templated types with the same 1713 /// base template, a string representation of the type difference will be 1714 /// emitted to the stream and return true. Otherwise, return false. 1715 bool Emit() { 1716 Tree.StartTraverse(); 1717 if (Tree.Empty()) 1718 return false; 1719 1720 TreeToString(); 1721 assert(!IsBold && "Bold is applied to end of string."); 1722 return true; 1723 } 1724 }; // end class TemplateDiff 1725 } // end namespace 1726 1727 /// FormatTemplateTypeDiff - A helper static function to start the template 1728 /// diff and return the properly formatted string. Returns true if the diff 1729 /// is successful. 1730 static bool FormatTemplateTypeDiff(ASTContext &Context, QualType FromType, 1731 QualType ToType, bool PrintTree, 1732 bool PrintFromType, bool ElideType, 1733 bool ShowColors, raw_ostream &OS) { 1734 if (PrintTree) 1735 PrintFromType = true; 1736 TemplateDiff TD(OS, Context, FromType, ToType, PrintTree, PrintFromType, 1737 ElideType, ShowColors); 1738 TD.DiffTemplate(); 1739 return TD.Emit(); 1740 } 1741
