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