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