bool ReduceClassTemplateParameter::isValidForReduction(
       const ClassTemplatePartialSpecializationDecl *PartialD)
{
  const ASTTemplateArgumentListInfo *ArgList = 
    PartialD->getTemplateArgsAsWritten();
  
  unsigned NumArgsAsWritten = ArgList->NumTemplateArgs;
  unsigned NumArgs = PartialD->getTemplateInstantiationArgs().size();

  if ((NumArgsAsWritten > 0) && 
      (TheParameterIndex >= NumArgsAsWritten) && 
      hasDefaultArg &&
      ((NumArgsAsWritten + 1) == NumArgs))  {

    return true;
  }

  if (NumArgsAsWritten != NumArgs)
    return false;

  const TemplateArgumentLoc *ArgLocs = ArgList->getTemplateArgs();
  for (unsigned AI = 0; AI < NumArgsAsWritten; ++AI) {
    if (AI == TheParameterIndex)
      continue;
    const TemplateArgumentLoc ArgLoc = ArgLocs[AI];
    TemplateArgument Arg = ArgLoc.getArgument();
    if (!referToAParameter(PartialD, Arg))
      return false;
  }

  return true;
}

bool ReduceClassTemplateParameter::reducePartialSpec(
       const ClassTemplatePartialSpecializationDecl *PartialD)
{
  const CXXRecordDecl *CXXRD = TheClassTemplateDecl->getTemplatedDecl();
  // it CXXRD has definition, skip it to avoid duplication
  if (CXXRD->hasDefinition())
    return false;

  if (!isValidForReduction(PartialD))
    return false;
  
  const ASTTemplateArgumentListInfo *ArgList = 
    PartialD->getTemplateArgsAsWritten();
  const TemplateArgumentLoc *ArgLocs = ArgList->getTemplateArgs();
  unsigned NumArgsAsWritten = ArgList->NumTemplateArgs;
  
  const TemplateArgumentLoc FirstArgLoc = ArgLocs[0];
  SourceRange FirstRange = FirstArgLoc.getSourceRange();
  SourceLocation StartLoc = FirstRange.getBegin();

  const TemplateArgumentLoc LastArgLoc = ArgLocs[NumArgsAsWritten - 1];
  SourceRange LastRange = LastArgLoc.getSourceRange();
  SourceLocation EndLoc = 
    RewriteHelper->getEndLocationUntil(LastRange, '>');

  RewriteHelper->removeTextFromLeftAt(SourceRange(StartLoc, EndLoc), '<', EndLoc);
  return true;
}

void ClassTemplateToClass::rewriteClassTemplatePartialSpecs(void)
{
  SmallVector<ClassTemplatePartialSpecializationDecl *, 10> PartialDecls;
  TheClassTemplateDecl->getPartialSpecializations(PartialDecls);

  for (SmallVector<ClassTemplatePartialSpecializationDecl *, 10>::iterator 
         I = PartialDecls.begin(), E = PartialDecls.end(); I != E; ++I) {
    const ClassTemplatePartialSpecializationDecl *PartialD = (*I);
    removeTemplateAndParameter(PartialD->getSourceRange().getBegin(), 
                               PartialD->getTemplateParameters());

    TemplateArgumentLoc *ArgLocs = PartialD->getTemplateArgsAsWritten();
    TransAssert(ArgLocs && "Invalid ArgLocs!");
    TemplateArgumentLoc FirstArgLoc = ArgLocs[0];
    SourceLocation StartLoc = FirstArgLoc.getSourceRange().getBegin();

    unsigned NumArgs = PartialD->getNumTemplateArgsAsWritten();
    TransAssert((NumArgs > 0) && "Invalid NumArgs!");
    TemplateArgumentLoc LastArgLoc = ArgLocs[NumArgs - 1];
    SourceRange LastRange = LastArgLoc.getSourceRange();
    SourceLocation EndLoc = RewriteHelper->getEndLocationUntil(LastRange, '>');
    
    RewriteHelper->removeTextFromLeftAt(SourceRange(StartLoc, EndLoc),
                                        '<', EndLoc);
  }
}

TemplateArgumentLoc
Sema::getTemplateArgumentPackExpansionPattern(
      TemplateArgumentLoc OrigLoc,
      SourceLocation &Ellipsis, Optional<unsigned> &NumExpansions) const {
  const TemplateArgument &Argument = OrigLoc.getArgument();
  assert(Argument.isPackExpansion());
  switch (Argument.getKind()) {
  case TemplateArgument::Type: {
    // FIXME: We shouldn't ever have to worry about missing
    // type-source info!
    TypeSourceInfo *ExpansionTSInfo = OrigLoc.getTypeSourceInfo();
    if (!ExpansionTSInfo)
      ExpansionTSInfo = Context.getTrivialTypeSourceInfo(Argument.getAsType(),
                                                         Ellipsis);
    PackExpansionTypeLoc Expansion =
        ExpansionTSInfo->getTypeLoc().castAs<PackExpansionTypeLoc>();
    Ellipsis = Expansion.getEllipsisLoc();

    TypeLoc Pattern = Expansion.getPatternLoc();
    NumExpansions = Expansion.getTypePtr()->getNumExpansions();

    // We need to copy the TypeLoc because TemplateArgumentLocs store a
    // TypeSourceInfo.
    // FIXME: Find some way to avoid the copy?
    TypeLocBuilder TLB;
    TLB.pushFullCopy(Pattern);
    TypeSourceInfo *PatternTSInfo =
        TLB.getTypeSourceInfo(Context, Pattern.getType());
    return TemplateArgumentLoc(TemplateArgument(Pattern.getType()),
                               PatternTSInfo);
  }

  case TemplateArgument::Expression: {
    PackExpansionExpr *Expansion
      = cast<PackExpansionExpr>(Argument.getAsExpr());
    Expr *Pattern = Expansion->getPattern();
    Ellipsis = Expansion->getEllipsisLoc();
    NumExpansions = Expansion->getNumExpansions();
    return TemplateArgumentLoc(Pattern, Pattern);
  }

  case TemplateArgument::TemplateExpansion:
    Ellipsis = OrigLoc.getTemplateEllipsisLoc();
    NumExpansions = Argument.getNumTemplateExpansions();
    return TemplateArgumentLoc(Argument.getPackExpansionPattern(),
                               OrigLoc.getTemplateQualifierLoc(),
                               OrigLoc.getTemplateNameLoc());

  case TemplateArgument::Declaration:
  case TemplateArgument::NullPtr:
  case TemplateArgument::Template:
  case TemplateArgument::Integral:
  case TemplateArgument::Pack:
  case TemplateArgument::Null:
    return TemplateArgumentLoc();
  }

  llvm_unreachable("Invalid TemplateArgument Kind!");
}

// ISSUE: The transformation is known to go wrong in the following case:
// template<typename T1, typename T2> struct S;
// template<typename T1, typename T2> struct S<T2, T1>;
void ReduceClassTemplateParameter::removeParameterFromPartialSpecs()
{
  SmallVector<ClassTemplatePartialSpecializationDecl *, 10> PartialDecls;
  TheClassTemplateDecl->getPartialSpecializations(PartialDecls);

  for (SmallVector<ClassTemplatePartialSpecializationDecl *, 10>::iterator 
         I = PartialDecls.begin(), E = PartialDecls.end(); I != E; ++I) {
    const ClassTemplatePartialSpecializationDecl *PartialD = (*I);
    
    const ASTTemplateArgumentListInfo *ArgList = 
      PartialD->getTemplateArgsAsWritten();
    const TemplateArgumentLoc *ArgLocs = ArgList->getTemplateArgs();
    unsigned NumArgs = ArgList->NumTemplateArgs;
    
    if (!ArgLocs)
      continue;

    // handle a special case where we could reduce a partial specialization
    // to a class template definition, e.g.:
    //   template<typename T1, typename T2> struct A;
    //   template<typename T1> struct A<T1, int> { };
    // ==>
    //   template<typename T1> struct A;
    //   template<typename T1> struct A { };
    if (reducePartialSpec(PartialD))
      continue;

    if ((TheParameterIndex >= NumArgs) && hasDefaultArg)
      return;

    TransAssert((TheParameterIndex < NumArgs) && 
                 "Bad NumArgs from partial template decl!");
    TemplateArgumentLoc ArgLoc = ArgLocs[TheParameterIndex];

    TemplateArgument Arg = ArgLoc.getArgument();
    removeOneParameterFromPartialDecl(PartialD, Arg);
     
    SourceRange Range = ArgLoc.getSourceRange();

    if (NumArgs == 1) {
      SourceLocation StartLoc = Range.getBegin();
      SourceLocation EndLoc = 
        RewriteHelper->getEndLocationUntil(Range, '>');
      EndLoc = EndLoc.getLocWithOffset(-1);
      TheRewriter.RemoveText(SourceRange(StartLoc, EndLoc));
    }
    else if ((TheParameterIndex + 1) == NumArgs) {
      // Seems there is no getRAngleLoc() utility for 
      // template arguments from a partial specialization
      SourceLocation EndLoc = 
        RewriteHelper->getEndLocationUntil(Range, '>');
      EndLoc = EndLoc.getLocWithOffset(-1);
      RewriteHelper->removeTextFromLeftAt(Range, ',', EndLoc);
    }
    else {
      RewriteHelper->removeTextUntil(Range, ',');
    }
  }
}

  bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &ArgLoc) {
    std::string ArgStr;
    llvm::raw_string_ostream Stream(ArgStr);
    const TemplateArgument &Arg = ArgLoc.getArgument();

    Arg.print(Context->getPrintingPolicy(), Stream);
    Match(Stream.str(), ArgLoc.getLocation());
    return ExpectedLocationVisitor<TemplateArgumentLocTraverser>::
      TraverseTemplateArgumentLoc(ArgLoc);
  }

bool Sema::DiagnoseUnexpandedParameterPack(TemplateArgumentLoc Arg,
                                         UnexpandedParameterPackContext UPPC) {
  if (Arg.getArgument().isNull() ||
      !Arg.getArgument().containsUnexpandedParameterPack())
    return false;

  SmallVector<UnexpandedParameterPack, 2> Unexpanded;
  CollectUnexpandedParameterPacksVisitor(Unexpanded)
    .TraverseTemplateArgumentLoc(Arg);
  assert(!Unexpanded.empty() && "Unable to find unexpanded parameter packs");
  return DiagnoseUnexpandedParameterPacks(Arg.getLocation(), UPPC, Unexpanded);
}

bool ReduceClassTemplateParameterRewriteVisitor::
       VisitTemplateSpecializationTypeLoc(TemplateSpecializationTypeLoc Loc)
{
  // Invalidation can be introduced by constructor's initialization list, e.g.:
  // template<typename T1, typename T2> class A { };
  // class B : public A<int, int> {
  //   int m;
  //   B(int x) : m(x) {}
  // };
  // In RecursiveASTVisitor.h, TraverseConstructorInitializer will visit the part
  // of initializing base class's, i.e. through base's default constructor 
  if (Loc.getBeginLoc().isInvalid())
    return true;
  const TemplateSpecializationType *Ty = 
    dyn_cast<TemplateSpecializationType>(Loc.getTypePtr());
  TransAssert(Ty && "Invalid TemplateSpecializationType!");

  TemplateName TmplName = Ty->getTemplateName();
  if (!ConsumerInstance->referToTheTemplateDecl(TmplName))
    return true;

  unsigned NumArgs = Loc.getNumArgs();
  // I would put a stronger assert here, i.e., 
  // " (ConsumerInstance->TheParameterIndex >= NumArgs) && 
  // ConsumerInstance->hasDefaultArg "
  // but sometimes ill-formed input could yield incomplete
  // info, e.g., for two template decls which refer to the same
  // template def, one decl could have a non-null default arg,
  // while another decl's default arg field could be null. 
  if (ConsumerInstance->TheParameterIndex >= NumArgs)
    return true;

  TransAssert((ConsumerInstance->TheParameterIndex < NumArgs) &&
              "TheParameterIndex cannot be greater than NumArgs!");
  TemplateArgumentLoc ArgLoc = Loc.getArgLoc(ConsumerInstance->TheParameterIndex);
  SourceRange Range = ArgLoc.getSourceRange();

  if (NumArgs == 1) {
    ConsumerInstance->TheRewriter.ReplaceText(SourceRange(Loc.getLAngleLoc(),
                                                          Loc.getRAngleLoc()),
                                              "<>");
  }
  else if ((ConsumerInstance->TheParameterIndex + 1) == NumArgs) {
    SourceLocation EndLoc = Loc.getRAngleLoc();
    EndLoc = EndLoc.getLocWithOffset(-1);
    ConsumerInstance->RewriteHelper->removeTextFromLeftAt(
                                       Range, ',', EndLoc);
  }
  else {
    ConsumerInstance->RewriteHelper->removeTextUntil(Range, ',');
  }
  return true;
}

void TemplateTemplateParmDecl::setDefaultArgument(
    const ASTContext &C, const TemplateArgumentLoc &DefArg) {
  if (DefArg.getArgument().isNull())
    DefaultArgument.set(nullptr);
  else
    DefaultArgument.set(new (C) TemplateArgumentLoc(DefArg));
}

void TemplateArgToInt::handleOneTemplateArgumentLoc(
       const TemplateArgumentLoc &ArgLoc)
{
  if (ArgLoc.getLocation().isInvalid())
    return;
  const TemplateArgument &Arg = ArgLoc.getArgument();

  if (Arg.getKind() != TemplateArgument::Type)
    return;
  const Type *Ty = Arg.getAsType().getTypePtr();
  if (!Ty->getAsCXXRecordDecl() && !Ty->getPointeeCXXRecordDecl())
    return;

  ValidInstanceNum++;
  if (ValidInstanceNum == TransformationCounter)
    TheTypeSourceInfo = ArgLoc.getTypeSourceInfo();
}

void TemplateNonTypeArgToInt::handleOneTemplateArgumentLoc(
       const TemplateArgumentLoc &ArgLoc)
{
  if (ArgLoc.getLocation().isInvalid())
    return;
  const TemplateArgument &Arg = ArgLoc.getArgument();

  if (!isValidTemplateArgument(Arg))
    return;

  ValidInstanceNum++;
  if (ValidInstanceNum == TransformationCounter) {
    TheExpr = ArgLoc.getLocInfo().getAsExpr();
    llvm::APSInt Result;
    if (!TheExpr->isValueDependent() &&
        TheExpr->EvaluateAsInt(Result, *Context)) {
      IntString = Result.toString(10);
    }
  }
}

void ASTDumper::dumpTemplateArgumentLoc(const TemplateArgumentLoc &A) {
  dumpTemplateArgument(A.getArgument(), A.getSourceRange());
}