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