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