contrib/llvm/tools/clang/lib/AST/ASTDiagnostic.cpp

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