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