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