ASTDiagnostic.cpp revision 5409d28b6167032696f4915bb765a6f7db579f3f 
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
15#include "clang/AST/ASTContext.h"
16#include "clang/AST/DeclObjC.h"
17#include "clang/AST/TemplateBase.h"
18#include "clang/AST/ExprCXX.h"
19#include "clang/AST/DeclTemplate.h"
20#include "clang/AST/Type.h"
21#include "llvm/ADT/SmallString.h"
22#include "llvm/Support/raw_ostream.h"
23
24using namespace clang;
25
26// Returns a desugared version of the QualType, and marks ShouldAKA as true
27// whenever we remove significant sugar from the type.
28static QualType Desugar(ASTContext &Context, QualType QT, bool &ShouldAKA) {
29  QualifierCollector QC;
30
31  while (true) {
32    const Type *Ty = QC.strip(QT);
33
34    // Don't aka just because we saw an elaborated type...
35    if (const ElaboratedType *ET = dyn_cast<ElaboratedType>(Ty)) {
36      QT = ET->desugar();
37      continue;
38    }
39    // ... or a paren type ...
40    if (const ParenType *PT = dyn_cast<ParenType>(Ty)) {
41      QT = PT->desugar();
42      continue;
43    }
44    // ...or a substituted template type parameter ...
45    if (const SubstTemplateTypeParmType *ST =
46          dyn_cast<SubstTemplateTypeParmType>(Ty)) {
47      QT = ST->desugar();
48      continue;
49    }
50    // ...or an attributed type...
51    if (const AttributedType *AT = dyn_cast<AttributedType>(Ty)) {
52      QT = AT->desugar();
53      continue;
54    }
55    // ... or an auto type.
56    if (const AutoType *AT = dyn_cast<AutoType>(Ty)) {
57      if (!AT->isSugared())
58        break;
59      QT = AT->desugar();
60      continue;
61    }
62
63    // Don't desugar template specializations, unless it's an alias template.
64    if (const TemplateSpecializationType *TST
65          = dyn_cast<TemplateSpecializationType>(Ty))
66      if (!TST->isTypeAlias())
67        break;
68
69    // Don't desugar magic Objective-C types.
70    if (QualType(Ty,0) == Context.getObjCIdType() ||
71        QualType(Ty,0) == Context.getObjCClassType() ||
72        QualType(Ty,0) == Context.getObjCSelType() ||
73        QualType(Ty,0) == Context.getObjCProtoType())
74      break;
75
76    // Don't desugar va_list.
77    if (QualType(Ty,0) == Context.getBuiltinVaListType())
78      break;
79
80    // Otherwise, do a single-step desugar.
81    QualType Underlying;
82    bool IsSugar = false;
83    switch (Ty->getTypeClass()) {
84#define ABSTRACT_TYPE(Class, Base)
85#define TYPE(Class, Base) \
86case Type::Class: { \
87const Class##Type *CTy = cast<Class##Type>(Ty); \
88if (CTy->isSugared()) { \
89IsSugar = true; \
90Underlying = CTy->desugar(); \
91} \
92break; \
93}
94#include "clang/AST/TypeNodes.def"
95    }
96
97    // If it wasn't sugared, we're done.
98    if (!IsSugar)
99      break;
100
101    // If the desugared type is a vector type, we don't want to expand
102    // it, it will turn into an attribute mess. People want their "vec4".
103    if (isa<VectorType>(Underlying))
104      break;
105
106    // Don't desugar through the primary typedef of an anonymous type.
107    if (const TagType *UTT = Underlying->getAs<TagType>())
108      if (const TypedefType *QTT = dyn_cast<TypedefType>(QT))
109        if (UTT->getDecl()->getTypedefNameForAnonDecl() == QTT->getDecl())
110          break;
111
112    // Record that we actually looked through an opaque type here.
113    ShouldAKA = true;
114    QT = Underlying;
115  }
116
117  // If we have a pointer-like type, desugar the pointee as well.
118  // FIXME: Handle other pointer-like types.
119  if (const PointerType *Ty = QT->getAs<PointerType>()) {
120    QT = Context.getPointerType(Desugar(Context, Ty->getPointeeType(),
121                                        ShouldAKA));
122  } else if (const LValueReferenceType *Ty = QT->getAs<LValueReferenceType>()) {
123    QT = Context.getLValueReferenceType(Desugar(Context, Ty->getPointeeType(),
124                                                ShouldAKA));
125  } else if (const RValueReferenceType *Ty = QT->getAs<RValueReferenceType>()) {
126    QT = Context.getRValueReferenceType(Desugar(Context, Ty->getPointeeType(),
127                                                ShouldAKA));
128  }
129
130  return QC.apply(Context, QT);
131}
132
133/// \brief Convert the given type to a string suitable for printing as part of
134/// a diagnostic.
135///
136/// There are four main criteria when determining whether we should have an
137/// a.k.a. clause when pretty-printing a type:
138///
139/// 1) Some types provide very minimal sugar that doesn't impede the
140///    user's understanding --- for example, elaborated type
141///    specifiers.  If this is all the sugar we see, we don't want an
142///    a.k.a. clause.
143/// 2) Some types are technically sugared but are much more familiar
144///    when seen in their sugared form --- for example, va_list,
145///    vector types, and the magic Objective C types.  We don't
146///    want to desugar these, even if we do produce an a.k.a. clause.
147/// 3) Some types may have already been desugared previously in this diagnostic.
148///    if this is the case, doing another "aka" would just be clutter.
149/// 4) Two different types within the same diagnostic have the same output
150///    string.  In this case, force an a.k.a with the desugared type when
151///    doing so will provide additional information.
152///
153/// \param Context the context in which the type was allocated
154/// \param Ty the type to print
155/// \param QualTypeVals pointer values to QualTypes which are used in the
156/// diagnostic message
157static std::string
158ConvertTypeToDiagnosticString(ASTContext &Context, QualType Ty,
159                              const DiagnosticsEngine::ArgumentValue *PrevArgs,
160                              unsigned NumPrevArgs,
161                              ArrayRef<intptr_t> QualTypeVals) {
162  // FIXME: Playing with std::string is really slow.
163  bool ForceAKA = false;
164  QualType CanTy = Ty.getCanonicalType();
165  std::string S = Ty.getAsString(Context.getPrintingPolicy());
166  std::string CanS = CanTy.getAsString(Context.getPrintingPolicy());
167
168  for (unsigned I = 0, E = QualTypeVals.size(); I != E; ++I) {
169    QualType CompareTy =
170        QualType::getFromOpaquePtr(reinterpret_cast<void*>(QualTypeVals[I]));
171    if (CompareTy.isNull())
172      continue;
173    if (CompareTy == Ty)
174      continue;  // Same types
175    QualType CompareCanTy = CompareTy.getCanonicalType();
176    if (CompareCanTy == CanTy)
177      continue;  // Same canonical types
178    std::string CompareS = CompareTy.getAsString(Context.getPrintingPolicy());
179    bool aka;
180    QualType CompareDesugar = Desugar(Context, CompareTy, aka);
181    std::string CompareDesugarStr =
182        CompareDesugar.getAsString(Context.getPrintingPolicy());
183    if (CompareS != S && CompareDesugarStr != S)
184      continue;  // The type string is different than the comparison string
185                 // and the desugared comparison string.
186    std::string CompareCanS =
187        CompareCanTy.getAsString(Context.getPrintingPolicy());
188
189    if (CompareCanS == CanS)
190      continue;  // No new info from canonical type
191
192    ForceAKA = true;
193    break;
194  }
195
196  // Check to see if we already desugared this type in this
197  // diagnostic.  If so, don't do it again.
198  bool Repeated = false;
199  for (unsigned i = 0; i != NumPrevArgs; ++i) {
200    // TODO: Handle ak_declcontext case.
201    if (PrevArgs[i].first == DiagnosticsEngine::ak_qualtype) {
202      void *Ptr = (void*)PrevArgs[i].second;
203      QualType PrevTy(QualType::getFromOpaquePtr(Ptr));
204      if (PrevTy == Ty) {
205        Repeated = true;
206        break;
207      }
208    }
209  }
210
211  // Consider producing an a.k.a. clause if removing all the direct
212  // sugar gives us something "significantly different".
213  if (!Repeated) {
214    bool ShouldAKA = false;
215    QualType DesugaredTy = Desugar(Context, Ty, ShouldAKA);
216    if (ShouldAKA || ForceAKA) {
217      if (DesugaredTy == Ty) {
218        DesugaredTy = Ty.getCanonicalType();
219      }
220      std::string akaStr = DesugaredTy.getAsString(Context.getPrintingPolicy());
221      if (akaStr != S) {
222        S = "'" + S + "' (aka '" + akaStr + "')";
223        return S;
224      }
225    }
226  }
227
228  S = "'" + S + "'";
229  return S;
230}
231
232static bool FormatTemplateTypeDiff(ASTContext &Context, QualType FromType,
233                                   QualType ToType, bool PrintTree,
234                                   bool PrintFromType, bool ElideType,
235                                   bool ShowColors, std::string &S);
236
237void clang::FormatASTNodeDiagnosticArgument(
238    DiagnosticsEngine::ArgumentKind Kind,
239    intptr_t Val,
240    const char *Modifier,
241    unsigned ModLen,
242    const char *Argument,
243    unsigned ArgLen,
244    const DiagnosticsEngine::ArgumentValue *PrevArgs,
245    unsigned NumPrevArgs,
246    SmallVectorImpl<char> &Output,
247    void *Cookie,
248    ArrayRef<intptr_t> QualTypeVals) {
249  ASTContext &Context = *static_cast<ASTContext*>(Cookie);
250
251  std::string S;
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, S)) {
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 templete 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      S = ConvertTypeToDiagnosticString(Context, Ty, PrevArgs, NumPrevArgs,
289                                        QualTypeVals);
290      NeedQuotes = false;
291      break;
292    }
293    case DiagnosticsEngine::ak_declarationname: {
294      DeclarationName N = DeclarationName::getFromOpaqueInteger(Val);
295      S = N.getAsString();
296
297      if (ModLen == 9 && !memcmp(Modifier, "objcclass", 9) && ArgLen == 0)
298        S = '+' + S;
299      else if (ModLen == 12 && !memcmp(Modifier, "objcinstance", 12)
300                && ArgLen==0)
301        S = '-' + S;
302      else
303        assert(ModLen == 0 && ArgLen == 0 &&
304               "Invalid modifier for DeclarationName argument");
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(S, Context.getPrintingPolicy(), Qualified);
318      break;
319    }
320    case DiagnosticsEngine::ak_nestednamespec: {
321      llvm::raw_string_ostream OS(S);
322      reinterpret_cast<NestedNameSpecifier*>(Val)->print(OS,
323                                                        Context.getPrintingPolicy());
324      NeedQuotes = false;
325      break;
326    }
327    case DiagnosticsEngine::ak_declcontext: {
328      DeclContext *DC = reinterpret_cast<DeclContext *> (Val);
329      assert(DC && "Should never have a null declaration context");
330
331      if (DC->isTranslationUnit()) {
332        // FIXME: Get these strings from some localized place
333        if (Context.getLangOpts().CPlusPlus)
334          S = "the global namespace";
335        else
336          S = "the global scope";
337      } else if (TypeDecl *Type = dyn_cast<TypeDecl>(DC)) {
338        S = ConvertTypeToDiagnosticString(Context,
339                                          Context.getTypeDeclType(Type),
340                                          PrevArgs, NumPrevArgs, QualTypeVals);
341      } else {
342        // FIXME: Get these strings from some localized place
343        NamedDecl *ND = cast<NamedDecl>(DC);
344        if (isa<NamespaceDecl>(ND))
345          S += "namespace ";
346        else if (isa<ObjCMethodDecl>(ND))
347          S += "method ";
348        else if (isa<FunctionDecl>(ND))
349          S += "function ";
350
351        S += "'";
352        ND->getNameForDiagnostic(S, Context.getPrintingPolicy(), true);
353        S += "'";
354      }
355      NeedQuotes = false;
356      break;
357    }
358  }
359
360  if (NeedQuotes)
361    Output.push_back('\'');
362
363  Output.append(S.begin(), S.end());
364
365  if (NeedQuotes)
366    Output.push_back('\'');
367}
368
369/// TemplateDiff - A class that constructs a pretty string for a pair of
370/// QualTypes.  For the pair of types, a diff tree will be created containing
371/// all the information about the templates and template arguments.  Afterwards,
372/// the tree is transformed to a string according to the options passed in.
373namespace {
374class TemplateDiff {
375  /// Context - The ASTContext which is used for comparing template arguments.
376  ASTContext &Context;
377
378  /// Policy - Used during expression printing.
379  PrintingPolicy Policy;
380
381  /// ElideType - Option to elide identical types.
382  bool ElideType;
383
384  /// PrintTree - Format output string as a tree.
385  bool PrintTree;
386
387  /// ShowColor - Diagnostics support color, so bolding will be used.
388  bool ShowColor;
389
390  /// FromType - When single type printing is selected, this is the type to be
391  /// be printed.  When tree printing is selected, this type will show up first
392  /// in the tree.
393  QualType FromType;
394
395  /// ToType - The type that FromType is compared to.  Only in tree printing
396  /// will this type be outputed.
397  QualType ToType;
398
399  /// Str - Storage for the output stream.
400  llvm::SmallString<128> Str;
401
402  /// OS - The stream used to construct the output strings.
403  llvm::raw_svector_ostream OS;
404
405  /// IsBold - Keeps track of the bold formatting for the output string.
406  bool IsBold;
407
408  /// DiffTree - A tree representation the differences between two types.
409  class DiffTree {
410    /// DiffNode - The root node stores the original type.  Each child node
411    /// stores template arguments of their parents.  For templated types, the
412    /// template decl is also stored.
413    struct DiffNode {
414      /// NextNode - The index of the next sibling node or 0.
415      unsigned NextNode;
416
417      /// ChildNode - The index of the first child node or 0.
418      unsigned ChildNode;
419
420      /// ParentNode - The index of the parent node.
421      unsigned ParentNode;
422
423      /// FromType, ToType - The type arguments.
424      QualType FromType, ToType;
425
426      /// FromExpr, ToExpr - The expression arguments.
427      Expr *FromExpr, *ToExpr;
428
429      /// FromTD, ToTD - The template decl for template template
430      /// arguments or the type arguments that are templates.
431      TemplateDecl *FromTD, *ToTD;
432
433      /// FromDefault, ToDefault - Whether the argument is a default argument.
434      bool FromDefault, ToDefault;
435
436      /// Same - Whether the two arguments evaluate to the same value.
437      bool Same;
438
439      DiffNode(unsigned ParentNode = 0)
440        : NextNode(0), ChildNode(0), ParentNode(ParentNode),
441          FromType(), ToType(), FromExpr(0), ToExpr(0), FromTD(0), ToTD(0),
442          FromDefault(false), ToDefault(false), Same(false) { }
443    };
444
445    /// FlatTree - A flattened tree used to store the DiffNodes.
446    llvm::SmallVector<DiffNode, 16> FlatTree;
447
448    /// CurrentNode - The index of the current node being used.
449    unsigned CurrentNode;
450
451    /// NextFreeNode - The index of the next unused node.  Used when creating
452    /// child nodes.
453    unsigned NextFreeNode;
454
455    /// ReadNode - The index of the current node being read.
456    unsigned ReadNode;
457
458  public:
459    DiffTree() :
460        CurrentNode(0), NextFreeNode(1) {
461      FlatTree.push_back(DiffNode());
462    }
463
464    // Node writing functions.
465    /// SetNode - Sets FromTD and ToTD of the current node.
466    void SetNode(TemplateDecl *FromTD, TemplateDecl *ToTD) {
467      FlatTree[CurrentNode].FromTD = FromTD;
468      FlatTree[CurrentNode].ToTD = ToTD;
469    }
470
471    /// SetNode - Sets FromType and ToType of the current node.
472    void SetNode(QualType FromType, QualType ToType) {
473      FlatTree[CurrentNode].FromType = FromType;
474      FlatTree[CurrentNode].ToType = ToType;
475    }
476
477    /// SetNode - Set FromExpr and ToExpr of the current node.
478    void SetNode(Expr *FromExpr, Expr *ToExpr) {
479      FlatTree[CurrentNode].FromExpr = FromExpr;
480      FlatTree[CurrentNode].ToExpr = ToExpr;
481    }
482
483    /// SetSame - Sets the same flag of the current node.
484    void SetSame(bool Same) {
485      FlatTree[CurrentNode].Same = Same;
486    }
487
488    /// SetDefault - Sets FromDefault and ToDefault flags of the current node.
489    void SetDefault(bool FromDefault, bool ToDefault) {
490      FlatTree[CurrentNode].FromDefault = FromDefault;
491      FlatTree[CurrentNode].ToDefault = ToDefault;
492    }
493
494    /// Up - Changes the node to the parent of the current node.
495    void Up() {
496      CurrentNode = FlatTree[CurrentNode].ParentNode;
497    }
498
499    /// AddNode - Adds a child node to the current node, then sets that node
500    /// node as the current node.
501    void AddNode() {
502      FlatTree.push_back(DiffNode(CurrentNode));
503      DiffNode &Node = FlatTree[CurrentNode];
504      if (Node.ChildNode == 0) {
505        // If a child node doesn't exist, add one.
506        Node.ChildNode = NextFreeNode;
507      } else {
508        // If a child node exists, find the last child node and add a
509        // next node to it.
510        unsigned i;
511        for (i = Node.ChildNode; FlatTree[i].NextNode != 0;
512             i = FlatTree[i].NextNode) {
513        }
514        FlatTree[i].NextNode = NextFreeNode;
515      }
516      CurrentNode = NextFreeNode;
517      ++NextFreeNode;
518    }
519
520    // Node reading functions.
521    /// StartTraverse - Prepares the tree for recursive traversal.
522    void StartTraverse() {
523      ReadNode = 0;
524      CurrentNode = NextFreeNode;
525      NextFreeNode = 0;
526    }
527
528    /// Parent - Move the current read node to its parent.
529    void Parent() {
530      ReadNode = FlatTree[ReadNode].ParentNode;
531    }
532
533    /// NodeIsTemplate - Returns true if a template decl is set, and types are
534    /// set.
535    bool NodeIsTemplate() {
536      return (FlatTree[ReadNode].FromTD &&
537              !FlatTree[ReadNode].ToType.isNull()) ||
538             (FlatTree[ReadNode].ToTD && !FlatTree[ReadNode].ToType.isNull());
539    }
540
541    /// NodeIsQualType - Returns true if a Qualtype is set.
542    bool NodeIsQualType() {
543      return !FlatTree[ReadNode].FromType.isNull() ||
544             !FlatTree[ReadNode].ToType.isNull();
545    }
546
547    /// NodeIsExpr - Returns true if an expr is set.
548    bool NodeIsExpr() {
549      return FlatTree[ReadNode].FromExpr || FlatTree[ReadNode].ToExpr;
550    }
551
552    /// NodeIsTemplateTemplate - Returns true if the argument is a template
553    /// template type.
554    bool NodeIsTemplateTemplate() {
555      return FlatTree[ReadNode].FromType.isNull() &&
556             FlatTree[ReadNode].ToType.isNull() &&
557             (FlatTree[ReadNode].FromTD || FlatTree[ReadNode].ToTD);
558    }
559
560    /// GetNode - Gets the FromType and ToType.
561    void GetNode(QualType &FromType, QualType &ToType) {
562      FromType = FlatTree[ReadNode].FromType;
563      ToType = FlatTree[ReadNode].ToType;
564    }
565
566    /// GetNode - Gets the FromExpr and ToExpr.
567    void GetNode(Expr *&FromExpr, Expr *&ToExpr) {
568      FromExpr = FlatTree[ReadNode].FromExpr;
569      ToExpr = FlatTree[ReadNode].ToExpr;
570    }
571
572    /// GetNode - Gets the FromTD and ToTD.
573    void GetNode(TemplateDecl *&FromTD, TemplateDecl *&ToTD) {
574      FromTD = FlatTree[ReadNode].FromTD;
575      ToTD = FlatTree[ReadNode].ToTD;
576    }
577
578    /// NodeIsSame - Returns true the arguments are the same.
579    bool NodeIsSame() {
580      return FlatTree[ReadNode].Same;
581    }
582
583    /// HasChildrend - Returns true if the node has children.
584    bool HasChildren() {
585      return FlatTree[ReadNode].ChildNode != 0;
586    }
587
588    /// MoveToChild - Moves from the current node to its child.
589    void MoveToChild() {
590      ReadNode = FlatTree[ReadNode].ChildNode;
591    }
592
593    /// AdvanceSibling - If there is a next sibling, advance to it and return
594    /// true.  Otherwise, return false.
595    bool AdvanceSibling() {
596      if (FlatTree[ReadNode].NextNode == 0)
597        return false;
598
599      ReadNode = FlatTree[ReadNode].NextNode;
600      return true;
601    }
602
603    /// HasNextSibling - Return true if the node has a next sibling.
604    bool HasNextSibling() {
605      return FlatTree[ReadNode].NextNode != 0;
606    }
607
608    /// FromDefault - Return true if the from argument is the default.
609    bool FromDefault() {
610      return FlatTree[ReadNode].FromDefault;
611    }
612
613    /// ToDefault - Return true if the to argument is the default.
614    bool ToDefault() {
615      return FlatTree[ReadNode].ToDefault;
616    }
617
618    /// Empty - Returns true if the tree has no information.
619    bool Empty() {
620      return !FlatTree[0].FromTD && !FlatTree[0].ToTD &&
621             !FlatTree[0].FromExpr && !FlatTree[0].ToExpr &&
622             FlatTree[0].FromType.isNull() && FlatTree[0].ToType.isNull();
623    }
624  };
625
626  DiffTree Tree;
627
628  /// TSTiterator - an iterator that is used to enter a
629  /// TemplateSpecializationType and read TemplateArguments inside template
630  /// parameter packs in order with the rest of the TemplateArguments.
631  struct TSTiterator {
632    typedef const TemplateArgument& reference;
633    typedef const TemplateArgument* pointer;
634
635    /// TST - the template specialization whose arguments this iterator
636    /// traverse over.
637    const TemplateSpecializationType *TST;
638
639    /// Index - the index of the template argument in TST.
640    unsigned Index;
641
642    /// CurrentTA - if CurrentTA is not the same as EndTA, then CurrentTA
643    /// points to a TemplateArgument within a parameter pack.
644    TemplateArgument::pack_iterator CurrentTA;
645
646    /// EndTA - the end iterator of a parameter pack
647    TemplateArgument::pack_iterator EndTA;
648
649    /// TSTiterator - Constructs an iterator and sets it to the first template
650    /// argument.
651    TSTiterator(const TemplateSpecializationType *TST)
652        : TST(TST), Index(0), CurrentTA(0), EndTA(0) {
653      if (isEnd()) return;
654
655      // Set to first template argument.  If not a parameter pack, done.
656      TemplateArgument TA = TST->getArg(0);
657      if (TA.getKind() != TemplateArgument::Pack) return;
658
659      // Start looking into the parameter pack.
660      CurrentTA = TA.pack_begin();
661      EndTA = TA.pack_end();
662
663      // Found a valid template argument.
664      if (CurrentTA != EndTA) return;
665
666      // Parameter pack is empty, use the increment to get to a valid
667      // template argument.
668      ++(*this);
669    }
670
671    /// isEnd - Returns true if the iterator is one past the end.
672    bool isEnd() const {
673      return Index == TST->getNumArgs();
674    }
675
676    /// &operator++ - Increment the iterator to the next template argument.
677    TSTiterator &operator++() {
678      assert(!isEnd() && "Iterator incremented past end of arguments.");
679
680      // If in a parameter pack, advance in the parameter pack.
681      if (CurrentTA != EndTA) {
682        ++CurrentTA;
683        if (CurrentTA != EndTA)
684          return *this;
685      }
686
687      // Loop until a template argument is found, or the end is reached.
688      while (true) {
689        // Advance to the next template argument.  Break if reached the end.
690        if (++Index == TST->getNumArgs()) break;
691
692        // If the TemplateArgument is not a parameter pack, done.
693        TemplateArgument TA = TST->getArg(Index);
694        if (TA.getKind() != TemplateArgument::Pack) break;
695
696        // Handle parameter packs.
697        CurrentTA = TA.pack_begin();
698        EndTA = TA.pack_end();
699
700        // If the parameter pack is empty, try to advance again.
701        if (CurrentTA != EndTA) break;
702      }
703      return *this;
704    }
705
706    /// operator* - Returns the appropriate TemplateArgument.
707    reference operator*() const {
708      assert(!isEnd() && "Index exceeds number of arguments.");
709      if (CurrentTA == EndTA)
710        return TST->getArg(Index);
711      else
712        return *CurrentTA;
713    }
714
715    /// operator-> - Allow access to the underlying TemplateArgument.
716    pointer operator->() const {
717      return &operator*();
718    }
719  };
720
721  // These functions build up the template diff tree, including functions to
722  // retrieve and compare template arguments.
723
724  static const TemplateSpecializationType * GetTemplateSpecializationType(
725      ASTContext &Context, QualType Ty) {
726    if (const TemplateSpecializationType *TST =
727            Ty->getAs<TemplateSpecializationType>())
728      return TST;
729
730    const RecordType *RT = Ty->getAs<RecordType>();
731
732    if (!RT)
733      return 0;
734
735    const ClassTemplateSpecializationDecl *CTSD =
736        dyn_cast<ClassTemplateSpecializationDecl>(RT->getDecl());
737
738    if (!CTSD)
739      return 0;
740
741    Ty = Context.getTemplateSpecializationType(
742             TemplateName(CTSD->getSpecializedTemplate()),
743             CTSD->getTemplateArgs().data(),
744             CTSD->getTemplateArgs().size(),
745             Ty.getCanonicalType());
746
747    return Ty->getAs<TemplateSpecializationType>();
748  }
749
750  /// DiffTemplate - recursively visits template arguments and stores the
751  /// argument info into a tree.
752  void DiffTemplate(const TemplateSpecializationType *FromTST,
753                    const TemplateSpecializationType *ToTST) {
754    // Begin descent into diffing template tree.
755    TemplateParameterList *Params =
756        FromTST->getTemplateName().getAsTemplateDecl()->getTemplateParameters();
757    unsigned TotalArgs = 0;
758    for (TSTiterator FromIter(FromTST), ToIter(ToTST);
759         !FromIter.isEnd() || !ToIter.isEnd(); ++TotalArgs) {
760      Tree.AddNode();
761
762      // Get the parameter at index TotalArgs.  If index is larger
763      // than the total number of parameters, then there is an
764      // argument pack, so re-use the last parameter.
765      NamedDecl *ParamND = Params->getParam(
766          (TotalArgs < Params->size()) ? TotalArgs
767                                       : Params->size() - 1);
768      // Handle Types
769      if (TemplateTypeParmDecl *DefaultTTPD =
770              dyn_cast<TemplateTypeParmDecl>(ParamND)) {
771        QualType FromType, ToType;
772        GetType(FromIter, DefaultTTPD, FromType);
773        GetType(ToIter, DefaultTTPD, ToType);
774        Tree.SetNode(FromType, ToType);
775        Tree.SetDefault(FromIter.isEnd() && !FromType.isNull(),
776                        ToIter.isEnd() && !ToType.isNull());
777        if (!FromType.isNull() && !ToType.isNull()) {
778          if (Context.hasSameType(FromType, ToType)) {
779            Tree.SetSame(true);
780          } else {
781            const TemplateSpecializationType *FromArgTST =
782                GetTemplateSpecializationType(Context, FromType);
783            const TemplateSpecializationType *ToArgTST =
784                GetTemplateSpecializationType(Context, ToType);
785
786            if (FromArgTST && ToArgTST) {
787              bool SameTemplate = hasSameTemplate(FromArgTST, ToArgTST);
788              if (SameTemplate) {
789                Tree.SetNode(FromArgTST->getTemplateName().getAsTemplateDecl(),
790                             ToArgTST->getTemplateName().getAsTemplateDecl());
791                DiffTemplate(FromArgTST, ToArgTST);
792              }
793            }
794          }
795        }
796      }
797
798      // Handle Expressions
799      if (NonTypeTemplateParmDecl *DefaultNTTPD =
800              dyn_cast<NonTypeTemplateParmDecl>(ParamND)) {
801        Expr *FromExpr, *ToExpr;
802        GetExpr(FromIter, DefaultNTTPD, FromExpr);
803        GetExpr(ToIter, DefaultNTTPD, ToExpr);
804        Tree.SetNode(FromExpr, ToExpr);
805        Tree.SetSame(IsEqualExpr(Context, FromExpr, ToExpr));
806        Tree.SetDefault(FromIter.isEnd() && FromExpr,
807                        ToIter.isEnd() && ToExpr);
808      }
809
810      // Handle Templates
811      if (TemplateTemplateParmDecl *DefaultTTPD =
812              dyn_cast<TemplateTemplateParmDecl>(ParamND)) {
813        TemplateDecl *FromDecl, *ToDecl;
814        GetTemplateDecl(FromIter, DefaultTTPD, FromDecl);
815        GetTemplateDecl(ToIter, DefaultTTPD, ToDecl);
816        Tree.SetNode(FromDecl, ToDecl);
817        Tree.SetSame(FromDecl && ToDecl &&
818                     FromDecl->getIdentifier() == ToDecl->getIdentifier());
819      }
820
821      if (!FromIter.isEnd()) ++FromIter;
822      if (!ToIter.isEnd()) ++ToIter;
823      Tree.Up();
824    }
825  }
826
827  /// hasSameTemplate - Returns true if both types are specialized from the
828  /// same template declaration.  If they come from different template aliases,
829  /// do a parallel ascension search to determine the highest template alias in
830  /// common and set the arguments to them.
831  static bool hasSameTemplate(const TemplateSpecializationType *&FromTST,
832                              const TemplateSpecializationType *&ToTST) {
833    // Check the top templates if they are the same.
834    if (FromTST->getTemplateName().getAsTemplateDecl()->getIdentifier() ==
835        ToTST->getTemplateName().getAsTemplateDecl()->getIdentifier())
836      return true;
837
838    // Create vectors of template aliases.
839    SmallVector<const TemplateSpecializationType*, 1> FromTemplateList,
840                                                      ToTemplateList;
841
842    const TemplateSpecializationType *TempToTST = ToTST, *TempFromTST = FromTST;
843    FromTemplateList.push_back(FromTST);
844    ToTemplateList.push_back(ToTST);
845
846    // Dump every template alias into the vectors.
847    while (TempFromTST->isTypeAlias()) {
848      TempFromTST =
849          TempFromTST->getAliasedType()->getAs<TemplateSpecializationType>();
850      if (!TempFromTST)
851        break;
852      FromTemplateList.push_back(TempFromTST);
853    }
854    while (TempToTST->isTypeAlias()) {
855      TempToTST =
856          TempToTST->getAliasedType()->getAs<TemplateSpecializationType>();
857      if (!TempToTST)
858        break;
859      ToTemplateList.push_back(TempToTST);
860    }
861
862    SmallVector<const TemplateSpecializationType*, 1>::reverse_iterator
863        FromIter = FromTemplateList.rbegin(), FromEnd = FromTemplateList.rend(),
864        ToIter = ToTemplateList.rbegin(), ToEnd = ToTemplateList.rend();
865
866    // Check if the lowest template types are the same.  If not, return.
867    if ((*FromIter)->getTemplateName().getAsTemplateDecl()->getIdentifier() !=
868        (*ToIter)->getTemplateName().getAsTemplateDecl()->getIdentifier())
869      return false;
870
871    // Begin searching up the template aliases.  The bottom most template
872    // matches so move up until one pair does not match.  Use the template
873    // right before that one.
874    for (; FromIter != FromEnd && ToIter != ToEnd; ++FromIter, ++ToIter) {
875      if ((*FromIter)->getTemplateName().getAsTemplateDecl()->getIdentifier() !=
876          (*ToIter)->getTemplateName().getAsTemplateDecl()->getIdentifier())
877        break;
878    }
879
880    FromTST = FromIter[-1];
881    ToTST = ToIter[-1];
882
883    return true;
884  }
885
886  /// GetType - Retrieves the template type arguments, including default
887  /// arguments.
888  void GetType(const TSTiterator &Iter, TemplateTypeParmDecl *DefaultTTPD,
889               QualType &ArgType) {
890    ArgType = QualType();
891    bool isVariadic = DefaultTTPD->isParameterPack();
892
893    if (!Iter.isEnd())
894      ArgType = Iter->getAsType();
895    else if (!isVariadic)
896      ArgType = DefaultTTPD->getDefaultArgument();
897  }
898
899  /// GetExpr - Retrieves the template expression argument, including default
900  /// arguments.
901  void GetExpr(const TSTiterator &Iter, NonTypeTemplateParmDecl *DefaultNTTPD,
902               Expr *&ArgExpr) {
903    ArgExpr = 0;
904    bool isVariadic = DefaultNTTPD->isParameterPack();
905
906    if (!Iter.isEnd())
907      ArgExpr = Iter->getAsExpr();
908    else if (!isVariadic)
909      ArgExpr = DefaultNTTPD->getDefaultArgument();
910
911    if (ArgExpr)
912      while (SubstNonTypeTemplateParmExpr *SNTTPE =
913                 dyn_cast<SubstNonTypeTemplateParmExpr>(ArgExpr))
914        ArgExpr = SNTTPE->getReplacement();
915  }
916
917  /// GetTemplateDecl - Retrieves the template template arguments, including
918  /// default arguments.
919  void GetTemplateDecl(const TSTiterator &Iter,
920                       TemplateTemplateParmDecl *DefaultTTPD,
921                       TemplateDecl *&ArgDecl) {
922    ArgDecl = 0;
923    bool isVariadic = DefaultTTPD->isParameterPack();
924
925    TemplateArgument TA = DefaultTTPD->getDefaultArgument().getArgument();
926    TemplateDecl *DefaultTD = TA.getAsTemplate().getAsTemplateDecl();
927
928    if (!Iter.isEnd())
929      ArgDecl = Iter->getAsTemplate().getAsTemplateDecl();
930    else if (!isVariadic)
931      ArgDecl = DefaultTD;
932  }
933
934  /// IsEqualExpr - Returns true if the expressions evaluate to the same value.
935  static bool IsEqualExpr(ASTContext &Context, Expr *FromExpr, Expr *ToExpr) {
936    if (FromExpr == ToExpr)
937      return true;
938
939    if (!FromExpr || !ToExpr)
940      return false;
941
942    FromExpr = FromExpr->IgnoreParens();
943    ToExpr = ToExpr->IgnoreParens();
944
945    DeclRefExpr *FromDRE = dyn_cast<DeclRefExpr>(FromExpr),
946                *ToDRE = dyn_cast<DeclRefExpr>(ToExpr);
947
948    if (FromDRE || ToDRE) {
949      if (!FromDRE || !ToDRE)
950        return false;
951      return FromDRE->getDecl() == ToDRE->getDecl();
952    }
953
954    Expr::EvalResult FromResult, ToResult;
955    if (!FromExpr->EvaluateAsRValue(FromResult, Context) ||
956        !ToExpr->EvaluateAsRValue(ToResult, Context))
957      assert(0 && "Template arguments must be known at compile time.");
958
959    APValue &FromVal = FromResult.Val;
960    APValue &ToVal = ToResult.Val;
961
962    if (FromVal.getKind() != ToVal.getKind()) return false;
963
964    switch (FromVal.getKind()) {
965      case APValue::Int:
966        return FromVal.getInt() == ToVal.getInt();
967      case APValue::LValue: {
968        APValue::LValueBase FromBase = FromVal.getLValueBase();
969        APValue::LValueBase ToBase = ToVal.getLValueBase();
970        if (FromBase.isNull() && ToBase.isNull())
971          return true;
972        if (FromBase.isNull() || ToBase.isNull())
973          return false;
974        return FromBase.get<const ValueDecl*>() ==
975               ToBase.get<const ValueDecl*>();
976      }
977      case APValue::MemberPointer:
978        return FromVal.getMemberPointerDecl() == ToVal.getMemberPointerDecl();
979      default:
980        llvm_unreachable("Unknown template argument expression.");
981    }
982  }
983
984  // These functions converts the tree representation of the template
985  // differences into the internal character vector.
986
987  /// TreeToString - Converts the Tree object into a character stream which
988  /// will later be turned into the output string.
989  void TreeToString(int Indent = 1) {
990    if (PrintTree) {
991      OS << '\n';
992      for (int i = 0; i < Indent; ++i)
993        OS << "  ";
994      ++Indent;
995    }
996
997    // Handle cases where the difference is not templates with different
998    // arguments.
999    if (!Tree.NodeIsTemplate()) {
1000      if (Tree.NodeIsQualType()) {
1001        QualType FromType, ToType;
1002        Tree.GetNode(FromType, ToType);
1003        PrintTypeNames(FromType, ToType, Tree.FromDefault(), Tree.ToDefault(),
1004                       Tree.NodeIsSame());
1005        return;
1006      }
1007      if (Tree.NodeIsExpr()) {
1008        Expr *FromExpr, *ToExpr;
1009        Tree.GetNode(FromExpr, ToExpr);
1010        PrintExpr(FromExpr, ToExpr, Tree.FromDefault(), Tree.ToDefault(),
1011                  Tree.NodeIsSame());
1012        return;
1013      }
1014      if (Tree.NodeIsTemplateTemplate()) {
1015        TemplateDecl *FromTD, *ToTD;
1016        Tree.GetNode(FromTD, ToTD);
1017        PrintTemplateTemplate(FromTD, ToTD, Tree.FromDefault(),
1018                              Tree.ToDefault(), Tree.NodeIsSame());
1019        return;
1020      }
1021      llvm_unreachable("Unable to deduce template difference.");
1022    }
1023
1024    // Node is root of template.  Recurse on children.
1025    TemplateDecl *FromTD, *ToTD;
1026    Tree.GetNode(FromTD, ToTD);
1027
1028    assert(Tree.HasChildren() && "Template difference not found in diff tree.");
1029
1030    OS << FromTD->getNameAsString() << '<';
1031    Tree.MoveToChild();
1032    unsigned NumElideArgs = 0;
1033    do {
1034      if (ElideType) {
1035        if (Tree.NodeIsSame()) {
1036          ++NumElideArgs;
1037          continue;
1038        }
1039        if (NumElideArgs > 0) {
1040          PrintElideArgs(NumElideArgs, Indent);
1041          NumElideArgs = 0;
1042          OS << ", ";
1043        }
1044      }
1045      TreeToString(Indent);
1046      if (Tree.HasNextSibling())
1047        OS << ", ";
1048    } while (Tree.AdvanceSibling());
1049    if (NumElideArgs > 0)
1050      PrintElideArgs(NumElideArgs, Indent);
1051
1052    Tree.Parent();
1053    OS << ">";
1054  }
1055
1056  // To signal to the text printer that a certain text needs to be bolded,
1057  // a special character is injected into the character stream which the
1058  // text printer will later strip out.
1059
1060  /// Bold - Start bolding text.
1061  void Bold() {
1062    assert(!IsBold && "Attempting to bold text that is already bold.");
1063    IsBold = true;
1064    if (ShowColor)
1065      OS << ToggleHighlight;
1066  }
1067
1068  /// Unbold - Stop bolding text.
1069  void Unbold() {
1070    assert(IsBold && "Attempting to remove bold from unbold text.");
1071    IsBold = false;
1072    if (ShowColor)
1073      OS << ToggleHighlight;
1074  }
1075
1076  // Functions to print out the arguments and highlighting the difference.
1077
1078  /// PrintTypeNames - prints the typenames, bolding differences.  Will detect
1079  /// typenames that are the same and attempt to disambiguate them by using
1080  /// canonical typenames.
1081  void PrintTypeNames(QualType FromType, QualType ToType,
1082                      bool FromDefault, bool ToDefault, bool Same) {
1083    assert((!FromType.isNull() || !ToType.isNull()) &&
1084           "Only one template argument may be missing.");
1085
1086    if (Same) {
1087      OS << FromType.getAsString();
1088      return;
1089    }
1090
1091    std::string FromTypeStr = FromType.isNull() ? "(no argument)"
1092                                                : FromType.getAsString();
1093    std::string ToTypeStr = ToType.isNull() ? "(no argument)"
1094                                            : ToType.getAsString();
1095    // Switch to canonical typename if it is better.
1096    // TODO: merge this with other aka printing above.
1097    if (FromTypeStr == ToTypeStr) {
1098      std::string FromCanTypeStr = FromType.getCanonicalType().getAsString();
1099      std::string ToCanTypeStr = ToType.getCanonicalType().getAsString();
1100      if (FromCanTypeStr != ToCanTypeStr) {
1101        FromTypeStr = FromCanTypeStr;
1102        ToTypeStr = ToCanTypeStr;
1103      }
1104    }
1105
1106    if (PrintTree) OS << '[';
1107    OS << (FromDefault ? "(default) " : "");
1108    Bold();
1109    OS << FromTypeStr;
1110    Unbold();
1111    if (PrintTree) {
1112      OS << " != " << (ToDefault ? "(default) " : "");
1113      Bold();
1114      OS << ToTypeStr;
1115      Unbold();
1116      OS << "]";
1117    }
1118    return;
1119  }
1120
1121  /// PrintExpr - Prints out the expr template arguments, highlighting argument
1122  /// differences.
1123  void PrintExpr(const Expr *FromExpr, const Expr *ToExpr,
1124                 bool FromDefault, bool ToDefault, bool Same) {
1125    assert((FromExpr || ToExpr) &&
1126            "Only one template argument may be missing.");
1127    if (Same) {
1128      PrintExpr(FromExpr);
1129    } else if (!PrintTree) {
1130      OS << (FromDefault ? "(default) " : "");
1131      Bold();
1132      PrintExpr(FromExpr);
1133      Unbold();
1134    } else {
1135      OS << (FromDefault ? "[(default) " : "[");
1136      Bold();
1137      PrintExpr(FromExpr);
1138      Unbold();
1139      OS << " != " << (ToDefault ? "(default) " : "");
1140      Bold();
1141      PrintExpr(ToExpr);
1142      Unbold();
1143      OS << ']';
1144    }
1145  }
1146
1147  /// PrintExpr - Actual formatting and printing of expressions.
1148  void PrintExpr(const Expr *E) {
1149    if (!E)
1150      OS << "(no argument)";
1151    else
1152      E->printPretty(OS, Context, 0, Policy); return;
1153  }
1154
1155  /// PrintTemplateTemplate - Handles printing of template template arguments,
1156  /// highlighting argument differences.
1157  void PrintTemplateTemplate(TemplateDecl *FromTD, TemplateDecl *ToTD,
1158                             bool FromDefault, bool ToDefault, bool Same) {
1159    assert((FromTD || ToTD) && "Only one template argument may be missing.");
1160    if (Same) {
1161      OS << "template " << FromTD->getNameAsString();
1162    } else if (!PrintTree) {
1163      OS << (FromDefault ? "(default) template " : "template ");
1164      Bold();
1165      OS << (FromTD ? FromTD->getNameAsString() : "(no argument)");
1166      Unbold();
1167    } else {
1168      OS << (FromDefault ? "[(default) template " : "[template ");
1169      Bold();
1170      OS << (FromTD ? FromTD->getNameAsString() : "(no argument)");
1171      Unbold();
1172      OS << " != " << (ToDefault ? "(default) template " : "template ");
1173      Bold();
1174      OS << (ToTD ? ToTD->getNameAsString() : "(no argument)");
1175      Unbold();
1176      OS << ']';
1177    }
1178  }
1179
1180  // Prints the appropriate placeholder for elided template arguments.
1181  void PrintElideArgs(unsigned NumElideArgs, unsigned Indent) {
1182    if (PrintTree) {
1183      OS << '\n';
1184      for (unsigned i = 0; i < Indent; ++i)
1185        OS << "  ";
1186    }
1187    if (NumElideArgs == 0) return;
1188    if (NumElideArgs == 1)
1189      OS << "[...]";
1190    else
1191      OS << "[" << NumElideArgs << " * ...]";
1192  }
1193
1194public:
1195
1196  TemplateDiff(ASTContext &Context, QualType FromType, QualType ToType,
1197               bool PrintTree, bool PrintFromType, bool ElideType,
1198               bool ShowColor)
1199    : Context(Context),
1200      Policy(Context.getLangOpts()),
1201      ElideType(ElideType),
1202      PrintTree(PrintTree),
1203      ShowColor(ShowColor),
1204      // When printing a single type, the FromType is the one printed.
1205      FromType(PrintFromType ? FromType : ToType),
1206      ToType(PrintFromType ? ToType : FromType),
1207      OS(Str),
1208      IsBold(false) {
1209  }
1210
1211  /// DiffTemplate - Start the template type diffing.
1212  void DiffTemplate() {
1213    const TemplateSpecializationType *FromOrigTST =
1214        GetTemplateSpecializationType(Context, FromType);
1215    const TemplateSpecializationType *ToOrigTST =
1216        GetTemplateSpecializationType(Context, ToType);
1217
1218    // Only checking templates.
1219    if (!FromOrigTST || !ToOrigTST)
1220      return;
1221
1222    // Different base templates.
1223    if (!hasSameTemplate(FromOrigTST, ToOrigTST)) {
1224      return;
1225    }
1226
1227    Tree.SetNode(FromType, ToType);
1228
1229    // Same base template, but different arguments.
1230    Tree.SetNode(FromOrigTST->getTemplateName().getAsTemplateDecl(),
1231                 ToOrigTST->getTemplateName().getAsTemplateDecl());
1232
1233    DiffTemplate(FromOrigTST, ToOrigTST);
1234  }
1235
1236  /// MakeString - When the two types given are templated types with the same
1237  /// base template, a string representation of the type difference will be
1238  /// loaded into S and return true.  Otherwise, return false.
1239  bool MakeString(std::string &S) {
1240    Tree.StartTraverse();
1241    if (Tree.Empty())
1242      return false;
1243
1244    TreeToString();
1245    assert(!IsBold && "Bold is applied to end of string.");
1246    S = OS.str();
1247    return true;
1248  }
1249}; // end class TemplateDiff
1250}  // end namespace
1251
1252/// FormatTemplateTypeDiff - A helper static function to start the template
1253/// diff and return the properly formatted string.  Returns true if the diff
1254/// is successful.
1255static bool FormatTemplateTypeDiff(ASTContext &Context, QualType FromType,
1256                                   QualType ToType, bool PrintTree,
1257                                   bool PrintFromType, bool ElideType,
1258                                   bool ShowColors, std::string &S) {
1259  if (PrintTree)
1260    PrintFromType = true;
1261  TemplateDiff TD(Context, FromType, ToType, PrintTree, PrintFromType,
1262                  ElideType, ShowColors);
1263  TD.DiffTemplate();
1264  return TD.MakeString(S);
1265}
1266