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