contrib/llvm/tools/clang/lib/Sema/SemaTemplateInstantiate.cpp

   1 //===------- SemaTemplateInstantiate.cpp - C++ Template Instantiation ------===/
   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 //  This file implements C++ template instantiation.
  10 //
  11 //===----------------------------------------------------------------------===/
  12
  13 #include "clang/Sema/SemaInternal.h"
  14 #include "TreeTransform.h"
  15 #include "clang/Sema/DeclSpec.h"
  16 #include "clang/Sema/Initialization.h"
  17 #include "clang/Sema/Lookup.h"
  18 #include "clang/Sema/Template.h"
  19 #include "clang/Sema/TemplateDeduction.h"
  20 #include "clang/AST/ASTConsumer.h"
  21 #include "clang/AST/ASTContext.h"
  22 #include "clang/AST/Expr.h"
  23 #include "clang/AST/DeclTemplate.h"
  24 #include "clang/Basic/LangOptions.h"
  25
  26 using namespace clang;
  27 using namespace sema;
  28
  29 //===----------------------------------------------------------------------===/
  30 // Template Instantiation Support
  31 //===----------------------------------------------------------------------===/
  32
  33 /// \brief Retrieve the template argument list(s) that should be used to
  34 /// instantiate the definition of the given declaration.
  35 ///
  36 /// \param D the declaration for which we are computing template instantiation
  37 /// arguments.
  38 ///
  39 /// \param Innermost if non-NULL, the innermost template argument list.
  40 ///
  41 /// \param RelativeToPrimary true if we should get the template
  42 /// arguments relative to the primary template, even when we're
  43 /// dealing with a specialization. This is only relevant for function
  44 /// template specializations.
  45 ///
  46 /// \param Pattern If non-NULL, indicates the pattern from which we will be
  47 /// instantiating the definition of the given declaration, \p D. This is
  48 /// used to determine the proper set of template instantiation arguments for
  49 /// friend function template specializations.
  50 MultiLevelTemplateArgumentList
  51 Sema::getTemplateInstantiationArgs(NamedDecl *D,
  52                                    const TemplateArgumentList *Innermost,
  53                                    bool RelativeToPrimary,
  54                                    const FunctionDecl *Pattern) {
  55   // Accumulate the set of template argument lists in this structure.
  56   MultiLevelTemplateArgumentList Result;
  57
  58   if (Innermost)
  59     Result.addOuterTemplateArguments(Innermost);
  60
  61   DeclContext *Ctx = dyn_cast<DeclContext>(D);
  62   if (!Ctx) {
  63     Ctx = D->getDeclContext();
  64
  65     // If we have a template template parameter with translation unit context,
  66     // then we're performing substitution into a default template argument of
  67     // this template template parameter before we've constructed the template
  68     // that will own this template template parameter. In this case, we
  69     // use empty template parameter lists for all of the outer templates
  70     // to avoid performing any substitutions.
  71     if (Ctx->isTranslationUnit()) {
  72       if (TemplateTemplateParmDecl *TTP
  73                                       = dyn_cast<TemplateTemplateParmDecl>(D)) {
  74         for (unsigned I = 0, N = TTP->getDepth() + 1; I != N; ++I)
  75           Result.addOuterTemplateArguments(0, 0);
  76         return Result;
  77       }
  78     }
  79   }
  80
  81   while (!Ctx->isFileContext()) {
  82     // Add template arguments from a class template instantiation.
  83     if (ClassTemplateSpecializationDecl *Spec
  84           = dyn_cast<ClassTemplateSpecializationDecl>(Ctx)) {
  85       // We're done when we hit an explicit specialization.
  86       if (Spec->getSpecializationKind() == TSK_ExplicitSpecialization &&
  87           !isa<ClassTemplatePartialSpecializationDecl>(Spec))
  88         break;
  89
  90       Result.addOuterTemplateArguments(&Spec->getTemplateInstantiationArgs());
  91
  92       // If this class template specialization was instantiated from a
  93       // specialized member that is a class template, we're done.
  94       assert(Spec->getSpecializedTemplate() && "No class template?");
  95       if (Spec->getSpecializedTemplate()->isMemberSpecialization())
  96         break;
  97     }
  98     // Add template arguments from a function template specialization.
  99     else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Ctx)) {
 100       if (!RelativeToPrimary &&
 101           (Function->getTemplateSpecializationKind() ==
 102                                                   TSK_ExplicitSpecialization &&
 103            !Function->getClassScopeSpecializationPattern()))
 104         break;
 105
 106       if (const TemplateArgumentList *TemplateArgs
 107             = Function->getTemplateSpecializationArgs()) {
 108         // Add the template arguments for this specialization.
 109         Result.addOuterTemplateArguments(TemplateArgs);
 110
 111         // If this function was instantiated from a specialized member that is
 112         // a function template, we're done.
 113         assert(Function->getPrimaryTemplate() && "No function template?");
 114         if (Function->getPrimaryTemplate()->isMemberSpecialization())
 115           break;
 116       } else if (FunctionTemplateDecl *FunTmpl
 117                                    = Function->getDescribedFunctionTemplate()) {
 118         // Add the "injected" template arguments.
 119         std::pair<const TemplateArgument *, unsigned>
 120           Injected = FunTmpl->getInjectedTemplateArgs();
 121         Result.addOuterTemplateArguments(Injected.first, Injected.second);
 122       }
 123
 124       // If this is a friend declaration and it declares an entity at
 125       // namespace scope, take arguments from its lexical parent
 126       // instead of its semantic parent, unless of course the pattern we're
 127       // instantiating actually comes from the file's context!
 128       if (Function->getFriendObjectKind() &&
 129           Function->getDeclContext()->isFileContext() &&
 130           (!Pattern || !Pattern->getLexicalDeclContext()->isFileContext())) {
 131         Ctx = Function->getLexicalDeclContext();
 132         RelativeToPrimary = false;
 133         continue;
 134       }
 135     } else if (CXXRecordDecl *Rec = dyn_cast<CXXRecordDecl>(Ctx)) {
 136       if (ClassTemplateDecl *ClassTemplate = Rec->getDescribedClassTemplate()) {
 137         QualType T = ClassTemplate->getInjectedClassNameSpecialization();
 138         const TemplateSpecializationType *TST
 139           = cast<TemplateSpecializationType>(Context.getCanonicalType(T));
 140         Result.addOuterTemplateArguments(TST->getArgs(), TST->getNumArgs());
 141         if (ClassTemplate->isMemberSpecialization())
 142           break;
 143       }
 144     }
 145
 146     Ctx = Ctx->getParent();
 147     RelativeToPrimary = false;
 148   }
 149
 150   return Result;
 151 }
 152
 153 bool Sema::ActiveTemplateInstantiation::isInstantiationRecord() const {
 154   switch (Kind) {
 155   case TemplateInstantiation:
 156   case ExceptionSpecInstantiation:
 157   case DefaultTemplateArgumentInstantiation:
 158   case DefaultFunctionArgumentInstantiation:
 159     return true;
 160
 161   case ExplicitTemplateArgumentSubstitution:
 162   case DeducedTemplateArgumentSubstitution:
 163   case PriorTemplateArgumentSubstitution:
 164   case DefaultTemplateArgumentChecking:
 165     return false;
 166   }
 167
 168   llvm_unreachable("Invalid InstantiationKind!");
 169 }
 170
 171 Sema::InstantiatingTemplate::
 172 InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
 173                       Decl *Entity,
 174                       SourceRange InstantiationRange)
 175   : SemaRef(SemaRef),
 176     SavedInNonInstantiationSFINAEContext(
 177                                         SemaRef.InNonInstantiationSFINAEContext)
 178 {
 179   Invalid = CheckInstantiationDepth(PointOfInstantiation,
 180                                     InstantiationRange);
 181   if (!Invalid) {
 182     ActiveTemplateInstantiation Inst;
 183     Inst.Kind = ActiveTemplateInstantiation::TemplateInstantiation;
 184     Inst.PointOfInstantiation = PointOfInstantiation;
 185     Inst.Entity = reinterpret_cast<uintptr_t>(Entity);
 186     Inst.TemplateArgs = 0;
 187     Inst.NumTemplateArgs = 0;
 188     Inst.InstantiationRange = InstantiationRange;
 189     SemaRef.InNonInstantiationSFINAEContext = false;
 190     SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 191   }
 192 }
 193
 194 Sema::InstantiatingTemplate::
 195 InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
 196                       FunctionDecl *Entity, ExceptionSpecification,
 197                       SourceRange InstantiationRange)
 198   : SemaRef(SemaRef),
 199     SavedInNonInstantiationSFINAEContext(
 200                                         SemaRef.InNonInstantiationSFINAEContext)
 201 {
 202   Invalid = CheckInstantiationDepth(PointOfInstantiation,
 203                                     InstantiationRange);
 204   if (!Invalid) {
 205     ActiveTemplateInstantiation Inst;
 206     Inst.Kind = ActiveTemplateInstantiation::ExceptionSpecInstantiation;
 207     Inst.PointOfInstantiation = PointOfInstantiation;
 208     Inst.Entity = reinterpret_cast<uintptr_t>(Entity);
 209     Inst.TemplateArgs = 0;
 210     Inst.NumTemplateArgs = 0;
 211     Inst.InstantiationRange = InstantiationRange;
 212     SemaRef.InNonInstantiationSFINAEContext = false;
 213     SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 214   }
 215 }
 216
 217 Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
 218                                          SourceLocation PointOfInstantiation,
 219                                          TemplateDecl *Template,
 220                                          const TemplateArgument *TemplateArgs,
 221                                          unsigned NumTemplateArgs,
 222                                          SourceRange InstantiationRange)
 223   : SemaRef(SemaRef),
 224     SavedInNonInstantiationSFINAEContext(
 225                                      SemaRef.InNonInstantiationSFINAEContext)
 226 {
 227   Invalid = CheckInstantiationDepth(PointOfInstantiation,
 228                                     InstantiationRange);
 229   if (!Invalid) {
 230     ActiveTemplateInstantiation Inst;
 231     Inst.Kind
 232       = ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation;
 233     Inst.PointOfInstantiation = PointOfInstantiation;
 234     Inst.Entity = reinterpret_cast<uintptr_t>(Template);
 235     Inst.TemplateArgs = TemplateArgs;
 236     Inst.NumTemplateArgs = NumTemplateArgs;
 237     Inst.InstantiationRange = InstantiationRange;
 238     SemaRef.InNonInstantiationSFINAEContext = false;
 239     SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 240   }
 241 }
 242
 243 Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
 244                                          SourceLocation PointOfInstantiation,
 245                                       FunctionTemplateDecl *FunctionTemplate,
 246                                         const TemplateArgument *TemplateArgs,
 247                                                    unsigned NumTemplateArgs,
 248                          ActiveTemplateInstantiation::InstantiationKind Kind,
 249                                    sema::TemplateDeductionInfo &DeductionInfo,
 250                                               SourceRange InstantiationRange)
 251   : SemaRef(SemaRef),
 252     SavedInNonInstantiationSFINAEContext(
 253                                      SemaRef.InNonInstantiationSFINAEContext)
 254 {
 255   Invalid = CheckInstantiationDepth(PointOfInstantiation,
 256                                     InstantiationRange);
 257   if (!Invalid) {
 258     ActiveTemplateInstantiation Inst;
 259     Inst.Kind = Kind;
 260     Inst.PointOfInstantiation = PointOfInstantiation;
 261     Inst.Entity = reinterpret_cast<uintptr_t>(FunctionTemplate);
 262     Inst.TemplateArgs = TemplateArgs;
 263     Inst.NumTemplateArgs = NumTemplateArgs;
 264     Inst.DeductionInfo = &DeductionInfo;
 265     Inst.InstantiationRange = InstantiationRange;
 266     SemaRef.InNonInstantiationSFINAEContext = false;
 267     SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 268
 269     if (!Inst.isInstantiationRecord())
 270       ++SemaRef.NonInstantiationEntries;
 271   }
 272 }
 273
 274 Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
 275                                          SourceLocation PointOfInstantiation,
 276                           ClassTemplatePartialSpecializationDecl *PartialSpec,
 277                                          const TemplateArgument *TemplateArgs,
 278                                          unsigned NumTemplateArgs,
 279                                     sema::TemplateDeductionInfo &DeductionInfo,
 280                                          SourceRange InstantiationRange)
 281   : SemaRef(SemaRef),
 282     SavedInNonInstantiationSFINAEContext(
 283                                      SemaRef.InNonInstantiationSFINAEContext)
 284 {
 285   Invalid = false;
 286
 287   ActiveTemplateInstantiation Inst;
 288   Inst.Kind = ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution;
 289   Inst.PointOfInstantiation = PointOfInstantiation;
 290   Inst.Entity = reinterpret_cast<uintptr_t>(PartialSpec);
 291   Inst.TemplateArgs = TemplateArgs;
 292   Inst.NumTemplateArgs = NumTemplateArgs;
 293   Inst.DeductionInfo = &DeductionInfo;
 294   Inst.InstantiationRange = InstantiationRange;
 295   SemaRef.InNonInstantiationSFINAEContext = false;
 296   SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 297
 298   assert(!Inst.isInstantiationRecord());
 299   ++SemaRef.NonInstantiationEntries;
 300 }
 301
 302 Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
 303                                           SourceLocation PointOfInstantiation,
 304                                           ParmVarDecl *Param,
 305                                           const TemplateArgument *TemplateArgs,
 306                                           unsigned NumTemplateArgs,
 307                                           SourceRange InstantiationRange)
 308   : SemaRef(SemaRef),
 309     SavedInNonInstantiationSFINAEContext(
 310                                      SemaRef.InNonInstantiationSFINAEContext)
 311 {
 312   Invalid = CheckInstantiationDepth(PointOfInstantiation, InstantiationRange);
 313
 314   if (!Invalid) {
 315     ActiveTemplateInstantiation Inst;
 316     Inst.Kind
 317       = ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation;
 318     Inst.PointOfInstantiation = PointOfInstantiation;
 319     Inst.Entity = reinterpret_cast<uintptr_t>(Param);
 320     Inst.TemplateArgs = TemplateArgs;
 321     Inst.NumTemplateArgs = NumTemplateArgs;
 322     Inst.InstantiationRange = InstantiationRange;
 323     SemaRef.InNonInstantiationSFINAEContext = false;
 324     SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 325   }
 326 }
 327
 328 Sema::InstantiatingTemplate::
 329 InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
 330                       NamedDecl *Template,
 331                       NonTypeTemplateParmDecl *Param,
 332                       const TemplateArgument *TemplateArgs,
 333                       unsigned NumTemplateArgs,
 334                       SourceRange InstantiationRange)
 335   : SemaRef(SemaRef),
 336     SavedInNonInstantiationSFINAEContext(
 337                                      SemaRef.InNonInstantiationSFINAEContext)
 338 {
 339   Invalid = false;
 340
 341   ActiveTemplateInstantiation Inst;
 342   Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
 343   Inst.PointOfInstantiation = PointOfInstantiation;
 344   Inst.Template = Template;
 345   Inst.Entity = reinterpret_cast<uintptr_t>(Param);
 346   Inst.TemplateArgs = TemplateArgs;
 347   Inst.NumTemplateArgs = NumTemplateArgs;
 348   Inst.InstantiationRange = InstantiationRange;
 349   SemaRef.InNonInstantiationSFINAEContext = false;
 350   SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 351
 352   assert(!Inst.isInstantiationRecord());
 353   ++SemaRef.NonInstantiationEntries;
 354 }
 355
 356 Sema::InstantiatingTemplate::
 357 InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
 358                       NamedDecl *Template,
 359                       TemplateTemplateParmDecl *Param,
 360                       const TemplateArgument *TemplateArgs,
 361                       unsigned NumTemplateArgs,
 362                       SourceRange InstantiationRange)
 363   : SemaRef(SemaRef),
 364     SavedInNonInstantiationSFINAEContext(
 365                                      SemaRef.InNonInstantiationSFINAEContext)
 366 {
 367   Invalid = false;
 368   ActiveTemplateInstantiation Inst;
 369   Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
 370   Inst.PointOfInstantiation = PointOfInstantiation;
 371   Inst.Template = Template;
 372   Inst.Entity = reinterpret_cast<uintptr_t>(Param);
 373   Inst.TemplateArgs = TemplateArgs;
 374   Inst.NumTemplateArgs = NumTemplateArgs;
 375   Inst.InstantiationRange = InstantiationRange;
 376   SemaRef.InNonInstantiationSFINAEContext = false;
 377   SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 378
 379   assert(!Inst.isInstantiationRecord());
 380   ++SemaRef.NonInstantiationEntries;
 381 }
 382
 383 Sema::InstantiatingTemplate::
 384 InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
 385                       TemplateDecl *Template,
 386                       NamedDecl *Param,
 387                       const TemplateArgument *TemplateArgs,
 388                       unsigned NumTemplateArgs,
 389                       SourceRange InstantiationRange)
 390   : SemaRef(SemaRef),
 391     SavedInNonInstantiationSFINAEContext(
 392                                      SemaRef.InNonInstantiationSFINAEContext)
 393 {
 394   Invalid = false;
 395
 396   ActiveTemplateInstantiation Inst;
 397   Inst.Kind = ActiveTemplateInstantiation::DefaultTemplateArgumentChecking;
 398   Inst.PointOfInstantiation = PointOfInstantiation;
 399   Inst.Template = Template;
 400   Inst.Entity = reinterpret_cast<uintptr_t>(Param);
 401   Inst.TemplateArgs = TemplateArgs;
 402   Inst.NumTemplateArgs = NumTemplateArgs;
 403   Inst.InstantiationRange = InstantiationRange;
 404   SemaRef.InNonInstantiationSFINAEContext = false;
 405   SemaRef.ActiveTemplateInstantiations.push_back(Inst);
 406
 407   assert(!Inst.isInstantiationRecord());
 408   ++SemaRef.NonInstantiationEntries;
 409 }
 410
 411 void Sema::InstantiatingTemplate::Clear() {
 412   if (!Invalid) {
 413     if (!SemaRef.ActiveTemplateInstantiations.back().isInstantiationRecord()) {
 414       assert(SemaRef.NonInstantiationEntries > 0);
 415       --SemaRef.NonInstantiationEntries;
 416     }
 417     SemaRef.InNonInstantiationSFINAEContext
 418       = SavedInNonInstantiationSFINAEContext;
 419     SemaRef.ActiveTemplateInstantiations.pop_back();
 420     Invalid = true;
 421   }
 422 }
 423
 424 bool Sema::InstantiatingTemplate::CheckInstantiationDepth(
 425                                         SourceLocation PointOfInstantiation,
 426                                            SourceRange InstantiationRange) {
 427   assert(SemaRef.NonInstantiationEntries <=
 428                                    SemaRef.ActiveTemplateInstantiations.size());
 429   if ((SemaRef.ActiveTemplateInstantiations.size() -
 430           SemaRef.NonInstantiationEntries)
 431         <= SemaRef.getLangOpts().InstantiationDepth)
 432     return false;
 433
 434   SemaRef.Diag(PointOfInstantiation,
 435                diag::err_template_recursion_depth_exceeded)
 436     << SemaRef.getLangOpts().InstantiationDepth
 437     << InstantiationRange;
 438   SemaRef.Diag(PointOfInstantiation, diag::note_template_recursion_depth)
 439     << SemaRef.getLangOpts().InstantiationDepth;
 440   return true;
 441 }
 442
 443 /// \brief Prints the current instantiation stack through a series of
 444 /// notes.
 445 void Sema::PrintInstantiationStack() {
 446   // Determine which template instantiations to skip, if any.
 447   unsigned SkipStart = ActiveTemplateInstantiations.size(), SkipEnd = SkipStart;
 448   unsigned Limit = Diags.getTemplateBacktraceLimit();
 449   if (Limit && Limit < ActiveTemplateInstantiations.size()) {
 450     SkipStart = Limit / 2 + Limit % 2;
 451     SkipEnd = ActiveTemplateInstantiations.size() - Limit / 2;
 452   }
 453
 454   // FIXME: In all of these cases, we need to show the template arguments
 455   unsigned InstantiationIdx = 0;
 456   for (SmallVector<ActiveTemplateInstantiation, 16>::reverse_iterator
 457          Active = ActiveTemplateInstantiations.rbegin(),
 458          ActiveEnd = ActiveTemplateInstantiations.rend();
 459        Active != ActiveEnd;
 460        ++Active, ++InstantiationIdx) {
 461     // Skip this instantiation?
 462     if (InstantiationIdx >= SkipStart && InstantiationIdx < SkipEnd) {
 463       if (InstantiationIdx == SkipStart) {
 464         // Note that we're skipping instantiations.
 465         Diags.Report(Active->PointOfInstantiation,
 466                      diag::note_instantiation_contexts_suppressed)
 467           << unsigned(ActiveTemplateInstantiations.size() - Limit);
 468       }
 469       continue;
 470     }
 471
 472     switch (Active->Kind) {
 473     case ActiveTemplateInstantiation::TemplateInstantiation: {
 474       Decl *D = reinterpret_cast<Decl *>(Active->Entity);
 475       if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D)) {
 476         unsigned DiagID = diag::note_template_member_class_here;
 477         if (isa<ClassTemplateSpecializationDecl>(Record))
 478           DiagID = diag::note_template_class_instantiation_here;
 479         Diags.Report(Active->PointOfInstantiation, DiagID)
 480           << Context.getTypeDeclType(Record)
 481           << Active->InstantiationRange;
 482       } else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D)) {
 483         unsigned DiagID;
 484         if (Function->getPrimaryTemplate())
 485           DiagID = diag::note_function_template_spec_here;
 486         else
 487           DiagID = diag::note_template_member_function_here;
 488         Diags.Report(Active->PointOfInstantiation, DiagID)
 489           << Function
 490           << Active->InstantiationRange;
 491       } else if (VarDecl *VD = dyn_cast<VarDecl>(D)) {
 492         Diags.Report(Active->PointOfInstantiation,
 493                      diag::note_template_static_data_member_def_here)
 494           << VD
 495           << Active->InstantiationRange;
 496       } else if (EnumDecl *ED = dyn_cast<EnumDecl>(D)) {
 497         Diags.Report(Active->PointOfInstantiation,
 498                      diag::note_template_enum_def_here)
 499           << ED
 500           << Active->InstantiationRange;
 501       } else {
 502         Diags.Report(Active->PointOfInstantiation,
 503                      diag::note_template_type_alias_instantiation_here)
 504           << cast<TypeAliasTemplateDecl>(D)
 505           << Active->InstantiationRange;
 506       }
 507       break;
 508     }
 509
 510     case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation: {
 511       TemplateDecl *Template = cast<TemplateDecl>((Decl *)Active->Entity);
 512       std::string TemplateArgsStr
 513         = TemplateSpecializationType::PrintTemplateArgumentList(
 514                                                          Active->TemplateArgs,
 515                                                       Active->NumTemplateArgs,
 516                                                       getPrintingPolicy());
 517       Diags.Report(Active->PointOfInstantiation,
 518                    diag::note_default_arg_instantiation_here)
 519         << (Template->getNameAsString() + TemplateArgsStr)
 520         << Active->InstantiationRange;
 521       break;
 522     }
 523
 524     case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution: {
 525       FunctionTemplateDecl *FnTmpl
 526         = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
 527       Diags.Report(Active->PointOfInstantiation,
 528                    diag::note_explicit_template_arg_substitution_here)
 529         << FnTmpl
 530         << getTemplateArgumentBindingsText(FnTmpl->getTemplateParameters(),
 531                                            Active->TemplateArgs,
 532                                            Active->NumTemplateArgs)
 533         << Active->InstantiationRange;
 534       break;
 535     }
 536
 537     case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
 538       if (ClassTemplatePartialSpecializationDecl *PartialSpec
 539             = dyn_cast<ClassTemplatePartialSpecializationDecl>(
 540                                                     (Decl *)Active->Entity)) {
 541         Diags.Report(Active->PointOfInstantiation,
 542                      diag::note_partial_spec_deduct_instantiation_here)
 543           << Context.getTypeDeclType(PartialSpec)
 544           << getTemplateArgumentBindingsText(
 545                                          PartialSpec->getTemplateParameters(),
 546                                              Active->TemplateArgs,
 547                                              Active->NumTemplateArgs)
 548           << Active->InstantiationRange;
 549       } else {
 550         FunctionTemplateDecl *FnTmpl
 551           = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
 552         Diags.Report(Active->PointOfInstantiation,
 553                      diag::note_function_template_deduction_instantiation_here)
 554           << FnTmpl
 555           << getTemplateArgumentBindingsText(FnTmpl->getTemplateParameters(),
 556                                              Active->TemplateArgs,
 557                                              Active->NumTemplateArgs)
 558           << Active->InstantiationRange;
 559       }
 560       break;
 561
 562     case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation: {
 563       ParmVarDecl *Param = cast<ParmVarDecl>((Decl *)Active->Entity);
 564       FunctionDecl *FD = cast<FunctionDecl>(Param->getDeclContext());
 565
 566       std::string TemplateArgsStr
 567         = TemplateSpecializationType::PrintTemplateArgumentList(
 568                                                          Active->TemplateArgs,
 569                                                       Active->NumTemplateArgs,
 570                                                       getPrintingPolicy());
 571       Diags.Report(Active->PointOfInstantiation,
 572                    diag::note_default_function_arg_instantiation_here)
 573         << (FD->getNameAsString() + TemplateArgsStr)
 574         << Active->InstantiationRange;
 575       break;
 576     }
 577
 578     case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution: {
 579       NamedDecl *Parm = cast<NamedDecl>((Decl *)Active->Entity);
 580       std::string Name;
 581       if (!Parm->getName().empty())
 582         Name = std::string(" '") + Parm->getName().str() + "'";
 583
 584       TemplateParameterList *TemplateParams = 0;
 585       if (TemplateDecl *Template = dyn_cast<TemplateDecl>(Active->Template))
 586         TemplateParams = Template->getTemplateParameters();
 587       else
 588         TemplateParams =
 589           cast<ClassTemplatePartialSpecializationDecl>(Active->Template)
 590                                                       ->getTemplateParameters();
 591       Diags.Report(Active->PointOfInstantiation,
 592                    diag::note_prior_template_arg_substitution)
 593         << isa<TemplateTemplateParmDecl>(Parm)
 594         << Name
 595         << getTemplateArgumentBindingsText(TemplateParams,
 596                                            Active->TemplateArgs,
 597                                            Active->NumTemplateArgs)
 598         << Active->InstantiationRange;
 599       break;
 600     }
 601
 602     case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking: {
 603       TemplateParameterList *TemplateParams = 0;
 604       if (TemplateDecl *Template = dyn_cast<TemplateDecl>(Active->Template))
 605         TemplateParams = Template->getTemplateParameters();
 606       else
 607         TemplateParams =
 608           cast<ClassTemplatePartialSpecializationDecl>(Active->Template)
 609                                                       ->getTemplateParameters();
 610
 611       Diags.Report(Active->PointOfInstantiation,
 612                    diag::note_template_default_arg_checking)
 613         << getTemplateArgumentBindingsText(TemplateParams,
 614                                            Active->TemplateArgs,
 615                                            Active->NumTemplateArgs)
 616         << Active->InstantiationRange;
 617       break;
 618     }
 619
 620     case ActiveTemplateInstantiation::ExceptionSpecInstantiation:
 621       Diags.Report(Active->PointOfInstantiation,
 622                    diag::note_template_exception_spec_instantiation_here)
 623         << cast<FunctionDecl>((Decl *)Active->Entity)
 624         << Active->InstantiationRange;
 625       break;
 626     }
 627   }
 628 }
 629
 630 llvm::Optional<TemplateDeductionInfo *> Sema::isSFINAEContext() const {
 631   if (InNonInstantiationSFINAEContext)
 632     return llvm::Optional<TemplateDeductionInfo *>(0);
 633
 634   for (SmallVector<ActiveTemplateInstantiation, 16>::const_reverse_iterator
 635          Active = ActiveTemplateInstantiations.rbegin(),
 636          ActiveEnd = ActiveTemplateInstantiations.rend();
 637        Active != ActiveEnd;
 638        ++Active)
 639   {
 640     switch(Active->Kind) {
 641     case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation:
 642     case ActiveTemplateInstantiation::TemplateInstantiation:
 643     case ActiveTemplateInstantiation::ExceptionSpecInstantiation:
 644       // This is a template instantiation, so there is no SFINAE.
 645       return llvm::Optional<TemplateDeductionInfo *>();
 646
 647     case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation:
 648     case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution:
 649     case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking:
 650       // A default template argument instantiation and substitution into
 651       // template parameters with arguments for prior parameters may or may
 652       // not be a SFINAE context; look further up the stack.
 653       break;
 654
 655     case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution:
 656     case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
 657       // We're either substitution explicitly-specified template arguments
 658       // or deduced template arguments, so SFINAE applies.
 659       assert(Active->DeductionInfo && "Missing deduction info pointer");
 660       return Active->DeductionInfo;
 661     }
 662   }
 663
 664   return llvm::Optional<TemplateDeductionInfo *>();
 665 }
 666
 667 /// \brief Retrieve the depth and index of a parameter pack.
 668 static std::pair<unsigned, unsigned>
 669 getDepthAndIndex(NamedDecl *ND) {
 670   if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(ND))
 671     return std::make_pair(TTP->getDepth(), TTP->getIndex());
 672
 673   if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(ND))
 674     return std::make_pair(NTTP->getDepth(), NTTP->getIndex());
 675
 676   TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(ND);
 677   return std::make_pair(TTP->getDepth(), TTP->getIndex());
 678 }
 679
 680 //===----------------------------------------------------------------------===/
 681 // Template Instantiation for Types
 682 //===----------------------------------------------------------------------===/
 683 namespace {
 684   class TemplateInstantiator : public TreeTransform<TemplateInstantiator> {
 685     const MultiLevelTemplateArgumentList &TemplateArgs;
 686     SourceLocation Loc;
 687     DeclarationName Entity;
 688
 689   public:
 690     typedef TreeTransform<TemplateInstantiator> inherited;
 691
 692     TemplateInstantiator(Sema &SemaRef,
 693                          const MultiLevelTemplateArgumentList &TemplateArgs,
 694                          SourceLocation Loc,
 695                          DeclarationName Entity)
 696       : inherited(SemaRef), TemplateArgs(TemplateArgs), Loc(Loc),
 697         Entity(Entity) { }
 698
 699     /// \brief Determine whether the given type \p T has already been
 700     /// transformed.
 701     ///
 702     /// For the purposes of template instantiation, a type has already been
 703     /// transformed if it is NULL or if it is not dependent.
 704     bool AlreadyTransformed(QualType T);
 705
 706     /// \brief Returns the location of the entity being instantiated, if known.
 707     SourceLocation getBaseLocation() { return Loc; }
 708
 709     /// \brief Returns the name of the entity being instantiated, if any.
 710     DeclarationName getBaseEntity() { return Entity; }
 711
 712     /// \brief Sets the "base" location and entity when that
 713     /// information is known based on another transformation.
 714     void setBase(SourceLocation Loc, DeclarationName Entity) {
 715       this->Loc = Loc;
 716       this->Entity = Entity;
 717     }
 718
 719     bool TryExpandParameterPacks(SourceLocation EllipsisLoc,
 720                                  SourceRange PatternRange,
 721                              llvm::ArrayRef<UnexpandedParameterPack> Unexpanded,
 722                                  bool &ShouldExpand,
 723                                  bool &RetainExpansion,
 724                                  llvm::Optional<unsigned> &NumExpansions) {
 725       return getSema().CheckParameterPacksForExpansion(EllipsisLoc,
 726                                                        PatternRange, Unexpanded,
 727                                                        TemplateArgs,
 728                                                        ShouldExpand,
 729                                                        RetainExpansion,
 730                                                        NumExpansions);
 731     }
 732
 733     void ExpandingFunctionParameterPack(ParmVarDecl *Pack) {
 734       SemaRef.CurrentInstantiationScope->MakeInstantiatedLocalArgPack(Pack);
 735     }
 736
 737     TemplateArgument ForgetPartiallySubstitutedPack() {
 738       TemplateArgument Result;
 739       if (NamedDecl *PartialPack
 740             = SemaRef.CurrentInstantiationScope->getPartiallySubstitutedPack()){
 741         MultiLevelTemplateArgumentList &TemplateArgs
 742           = const_cast<MultiLevelTemplateArgumentList &>(this->TemplateArgs);
 743         unsigned Depth, Index;
 744         llvm::tie(Depth, Index) = getDepthAndIndex(PartialPack);
 745         if (TemplateArgs.hasTemplateArgument(Depth, Index)) {
 746           Result = TemplateArgs(Depth, Index);
 747           TemplateArgs.setArgument(Depth, Index, TemplateArgument());
 748         }
 749       }
 750
 751       return Result;
 752     }
 753
 754     void RememberPartiallySubstitutedPack(TemplateArgument Arg) {
 755       if (Arg.isNull())
 756         return;
 757
 758       if (NamedDecl *PartialPack
 759             = SemaRef.CurrentInstantiationScope->getPartiallySubstitutedPack()){
 760         MultiLevelTemplateArgumentList &TemplateArgs
 761         = const_cast<MultiLevelTemplateArgumentList &>(this->TemplateArgs);
 762         unsigned Depth, Index;
 763         llvm::tie(Depth, Index) = getDepthAndIndex(PartialPack);
 764         TemplateArgs.setArgument(Depth, Index, Arg);
 765       }
 766     }
 767
 768     /// \brief Transform the given declaration by instantiating a reference to
 769     /// this declaration.
 770     Decl *TransformDecl(SourceLocation Loc, Decl *D);
 771
 772     void transformAttrs(Decl *Old, Decl *New) {
 773       SemaRef.InstantiateAttrs(TemplateArgs, Old, New);
 774     }
 775
 776     void transformedLocalDecl(Decl *Old, Decl *New) {
 777       SemaRef.CurrentInstantiationScope->InstantiatedLocal(Old, New);
 778     }
 779
 780     /// \brief Transform the definition of the given declaration by
 781     /// instantiating it.
 782     Decl *TransformDefinition(SourceLocation Loc, Decl *D);
 783
 784     /// \bried Transform the first qualifier within a scope by instantiating the
 785     /// declaration.
 786     NamedDecl *TransformFirstQualifierInScope(NamedDecl *D, SourceLocation Loc);
 787
 788     /// \brief Rebuild the exception declaration and register the declaration
 789     /// as an instantiated local.
 790     VarDecl *RebuildExceptionDecl(VarDecl *ExceptionDecl,
 791                                   TypeSourceInfo *Declarator,
 792                                   SourceLocation StartLoc,
 793                                   SourceLocation NameLoc,
 794                                   IdentifierInfo *Name);
 795
 796     /// \brief Rebuild the Objective-C exception declaration and register the
 797     /// declaration as an instantiated local.
 798     VarDecl *RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
 799                                       TypeSourceInfo *TSInfo, QualType T);
 800
 801     /// \brief Check for tag mismatches when instantiating an
 802     /// elaborated type.
 803     QualType RebuildElaboratedType(SourceLocation KeywordLoc,
 804                                    ElaboratedTypeKeyword Keyword,
 805                                    NestedNameSpecifierLoc QualifierLoc,
 806                                    QualType T);
 807
 808     TemplateName TransformTemplateName(CXXScopeSpec &SS,
 809                                        TemplateName Name,
 810                                        SourceLocation NameLoc,
 811                                        QualType ObjectType = QualType(),
 812                                        NamedDecl *FirstQualifierInScope = 0);
 813
 814     ExprResult TransformPredefinedExpr(PredefinedExpr *E);
 815     ExprResult TransformDeclRefExpr(DeclRefExpr *E);
 816     ExprResult TransformCXXDefaultArgExpr(CXXDefaultArgExpr *E);
 817     ExprResult TransformTemplateParmRefExpr(DeclRefExpr *E,
 818                                             NonTypeTemplateParmDecl *D);
 819     ExprResult TransformSubstNonTypeTemplateParmPackExpr(
 820                                            SubstNonTypeTemplateParmPackExpr *E);
 821
 822     QualType TransformFunctionProtoType(TypeLocBuilder &TLB,
 823                                         FunctionProtoTypeLoc TL);
 824     QualType TransformFunctionProtoType(TypeLocBuilder &TLB,
 825                                         FunctionProtoTypeLoc TL,
 826                                         CXXRecordDecl *ThisContext,
 827                                         unsigned ThisTypeQuals);
 828
 829     ParmVarDecl *TransformFunctionTypeParam(ParmVarDecl *OldParm,
 830                                             int indexAdjustment,
 831                                         llvm::Optional<unsigned> NumExpansions,
 832                                             bool ExpectParameterPack);
 833
 834     /// \brief Transforms a template type parameter type by performing
 835     /// substitution of the corresponding template type argument.
 836     QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
 837                                            TemplateTypeParmTypeLoc TL);
 838
 839     /// \brief Transforms an already-substituted template type parameter pack
 840     /// into either itself (if we aren't substituting into its pack expansion)
 841     /// or the appropriate substituted argument.
 842     QualType TransformSubstTemplateTypeParmPackType(TypeLocBuilder &TLB,
 843                                            SubstTemplateTypeParmPackTypeLoc TL);
 844
 845     ExprResult TransformCallExpr(CallExpr *CE) {
 846       getSema().CallsUndergoingInstantiation.push_back(CE);
 847       ExprResult Result =
 848           TreeTransform<TemplateInstantiator>::TransformCallExpr(CE);
 849       getSema().CallsUndergoingInstantiation.pop_back();
 850       return move(Result);
 851     }
 852
 853   private:
 854     ExprResult transformNonTypeTemplateParmRef(NonTypeTemplateParmDecl *parm,
 855                                                SourceLocation loc,
 856                                                const TemplateArgument &arg);
 857   };
 858 }
 859
 860 bool TemplateInstantiator::AlreadyTransformed(QualType T) {
 861   if (T.isNull())
 862     return true;
 863
 864   if (T->isInstantiationDependentType() || T->isVariablyModifiedType())
 865     return false;
 866
 867   getSema().MarkDeclarationsReferencedInType(Loc, T);
 868   return true;
 869 }
 870
 871 Decl *TemplateInstantiator::TransformDecl(SourceLocation Loc, Decl *D) {
 872   if (!D)
 873     return 0;
 874
 875   if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
 876     if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
 877       // If the corresponding template argument is NULL or non-existent, it's
 878       // because we are performing instantiation from explicitly-specified
 879       // template arguments in a function template, but there were some
 880       // arguments left unspecified.
 881       if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
 882                                             TTP->getPosition()))
 883         return D;
 884
 885       TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getPosition());
 886
 887       if (TTP->isParameterPack()) {
 888         assert(Arg.getKind() == TemplateArgument::Pack &&
 889                "Missing argument pack");
 890
 891         assert(getSema().ArgumentPackSubstitutionIndex >= 0);
 892         assert(getSema().ArgumentPackSubstitutionIndex < (int)Arg.pack_size());
 893         Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
 894       }
 895
 896       TemplateName Template = Arg.getAsTemplate();
 897       assert(!Template.isNull() && Template.getAsTemplateDecl() &&
 898              "Wrong kind of template template argument");
 899       return Template.getAsTemplateDecl();
 900     }
 901
 902     // Fall through to find the instantiated declaration for this template
 903     // template parameter.
 904   }
 905
 906   return SemaRef.FindInstantiatedDecl(Loc, cast<NamedDecl>(D), TemplateArgs);
 907 }
 908
 909 Decl *TemplateInstantiator::TransformDefinition(SourceLocation Loc, Decl *D) {
 910   Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
 911   if (!Inst)
 912     return 0;
 913
 914   getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
 915   return Inst;
 916 }
 917
 918 NamedDecl *
 919 TemplateInstantiator::TransformFirstQualifierInScope(NamedDecl *D,
 920                                                      SourceLocation Loc) {
 921   // If the first part of the nested-name-specifier was a template type
 922   // parameter, instantiate that type parameter down to a tag type.
 923   if (TemplateTypeParmDecl *TTPD = dyn_cast_or_null<TemplateTypeParmDecl>(D)) {
 924     const TemplateTypeParmType *TTP
 925       = cast<TemplateTypeParmType>(getSema().Context.getTypeDeclType(TTPD));
 926
 927     if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
 928       // FIXME: This needs testing w/ member access expressions.
 929       TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getIndex());
 930
 931       if (TTP->isParameterPack()) {
 932         assert(Arg.getKind() == TemplateArgument::Pack &&
 933                "Missing argument pack");
 934
 935         if (getSema().ArgumentPackSubstitutionIndex == -1)
 936           return 0;
 937
 938         assert(getSema().ArgumentPackSubstitutionIndex < (int)Arg.pack_size());
 939         Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
 940       }
 941
 942       QualType T = Arg.getAsType();
 943       if (T.isNull())
 944         return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
 945
 946       if (const TagType *Tag = T->getAs<TagType>())
 947         return Tag->getDecl();
 948
 949       // The resulting type is not a tag; complain.
 950       getSema().Diag(Loc, diag::err_nested_name_spec_non_tag) << T;
 951       return 0;
 952     }
 953   }
 954
 955   return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
 956 }
 957
 958 VarDecl *
 959 TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
 960                                            TypeSourceInfo *Declarator,
 961                                            SourceLocation StartLoc,
 962                                            SourceLocation NameLoc,
 963                                            IdentifierInfo *Name) {
 964   VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, Declarator,
 965                                                  StartLoc, NameLoc, Name);
 966   if (Var)
 967     getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
 968   return Var;
 969 }
 970
 971 VarDecl *TemplateInstantiator::RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
 972                                                         TypeSourceInfo *TSInfo,
 973                                                         QualType T) {
 974   VarDecl *Var = inherited::RebuildObjCExceptionDecl(ExceptionDecl, TSInfo, T);
 975   if (Var)
 976     getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
 977   return Var;
 978 }
 979
 980 QualType
 981 TemplateInstantiator::RebuildElaboratedType(SourceLocation KeywordLoc,
 982                                             ElaboratedTypeKeyword Keyword,
 983                                             NestedNameSpecifierLoc QualifierLoc,
 984                                             QualType T) {
 985   if (const TagType *TT = T->getAs<TagType>()) {
 986     TagDecl* TD = TT->getDecl();
 987
 988     SourceLocation TagLocation = KeywordLoc;
 989
 990     // FIXME: type might be anonymous.
 991     IdentifierInfo *Id = TD->getIdentifier();
 992
 993     // TODO: should we even warn on struct/class mismatches for this?  Seems
 994     // like it's likely to produce a lot of spurious errors.
 995     if (Keyword != ETK_None && Keyword != ETK_Typename) {
 996       TagTypeKind Kind = TypeWithKeyword::getTagTypeKindForKeyword(Keyword);
 997       if (!SemaRef.isAcceptableTagRedeclaration(TD, Kind, /*isDefinition*/false,
 998                                                 TagLocation, *Id)) {
 999         SemaRef.Diag(TagLocation, diag::err_use_with_wrong_tag)
1000           << Id
1001           << FixItHint::CreateReplacement(SourceRange(TagLocation),
1002                                           TD->getKindName());
1003         SemaRef.Diag(TD->getLocation(), diag::note_previous_use);
1004       }
1005     }
1006   }
1007
1008   return TreeTransform<TemplateInstantiator>::RebuildElaboratedType(KeywordLoc,
1009                                                                     Keyword,
1010                                                                   QualifierLoc,
1011                                                                     T);
1012 }
1013
1014 TemplateName TemplateInstantiator::TransformTemplateName(CXXScopeSpec &SS,
1015                                                          TemplateName Name,
1016                                                          SourceLocation NameLoc,
1017                                                          QualType ObjectType,
1018                                              NamedDecl *FirstQualifierInScope) {
1019   if (TemplateTemplateParmDecl *TTP
1020        = dyn_cast_or_null<TemplateTemplateParmDecl>(Name.getAsTemplateDecl())) {
1021     if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
1022       // If the corresponding template argument is NULL or non-existent, it's
1023       // because we are performing instantiation from explicitly-specified
1024       // template arguments in a function template, but there were some
1025       // arguments left unspecified.
1026       if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
1027                                             TTP->getPosition()))
1028         return Name;
1029
1030       TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getPosition());
1031
1032       if (TTP->isParameterPack()) {
1033         assert(Arg.getKind() == TemplateArgument::Pack &&
1034                "Missing argument pack");
1035
1036         if (getSema().ArgumentPackSubstitutionIndex == -1) {
1037           // We have the template argument pack to substitute, but we're not
1038           // actually expanding the enclosing pack expansion yet. So, just
1039           // keep the entire argument pack.
1040           return getSema().Context.getSubstTemplateTemplateParmPack(TTP, Arg);
1041         }
1042
1043         assert(getSema().ArgumentPackSubstitutionIndex < (int)Arg.pack_size());
1044         Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
1045       }
1046
1047       TemplateName Template = Arg.getAsTemplate();
1048       assert(!Template.isNull() && "Null template template argument");
1049
1050       // We don't ever want to substitute for a qualified template name, since
1051       // the qualifier is handled separately. So, look through the qualified
1052       // template name to its underlying declaration.
1053       if (QualifiedTemplateName *QTN = Template.getAsQualifiedTemplateName())
1054         Template = TemplateName(QTN->getTemplateDecl());
1055
1056       Template = getSema().Context.getSubstTemplateTemplateParm(TTP, Template);
1057       return Template;
1058     }
1059   }
1060
1061   if (SubstTemplateTemplateParmPackStorage *SubstPack
1062       = Name.getAsSubstTemplateTemplateParmPack()) {
1063     if (getSema().ArgumentPackSubstitutionIndex == -1)
1064       return Name;
1065
1066     const TemplateArgument &ArgPack = SubstPack->getArgumentPack();
1067     assert(getSema().ArgumentPackSubstitutionIndex < (int)ArgPack.pack_size() &&
1068            "Pack substitution index out-of-range");
1069     return ArgPack.pack_begin()[getSema().ArgumentPackSubstitutionIndex]
1070     .getAsTemplate();
1071   }
1072
1073   return inherited::TransformTemplateName(SS, Name, NameLoc, ObjectType,
1074                                           FirstQualifierInScope);
1075 }
1076
1077 ExprResult
1078 TemplateInstantiator::TransformPredefinedExpr(PredefinedExpr *E) {
1079   if (!E->isTypeDependent())
1080     return SemaRef.Owned(E);
1081
1082   FunctionDecl *currentDecl = getSema().getCurFunctionDecl();
1083   assert(currentDecl && "Must have current function declaration when "
1084                         "instantiating.");
1085
1086   PredefinedExpr::IdentType IT = E->getIdentType();
1087
1088   unsigned Length = PredefinedExpr::ComputeName(IT, currentDecl).length();
1089
1090   llvm::APInt LengthI(32, Length + 1);
1091   QualType ResTy = getSema().Context.CharTy.withConst();
1092   ResTy = getSema().Context.getConstantArrayType(ResTy, LengthI,
1093                                                  ArrayType::Normal, 0);
1094   PredefinedExpr *PE =
1095     new (getSema().Context) PredefinedExpr(E->getLocation(), ResTy, IT);
1096   return getSema().Owned(PE);
1097 }
1098
1099 ExprResult
1100 TemplateInstantiator::TransformTemplateParmRefExpr(DeclRefExpr *E,
1101                                                NonTypeTemplateParmDecl *NTTP) {
1102   // If the corresponding template argument is NULL or non-existent, it's
1103   // because we are performing instantiation from explicitly-specified
1104   // template arguments in a function template, but there were some
1105   // arguments left unspecified.
1106   if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
1107                                         NTTP->getPosition()))
1108     return SemaRef.Owned(E);
1109
1110   TemplateArgument Arg = TemplateArgs(NTTP->getDepth(), NTTP->getPosition());
1111   if (NTTP->isParameterPack()) {
1112     assert(Arg.getKind() == TemplateArgument::Pack &&
1113            "Missing argument pack");
1114
1115     if (getSema().ArgumentPackSubstitutionIndex == -1) {
1116       // We have an argument pack, but we can't select a particular argument
1117       // out of it yet. Therefore, we'll build an expression to hold on to that
1118       // argument pack.
1119       QualType TargetType = SemaRef.SubstType(NTTP->getType(), TemplateArgs,
1120                                               E->getLocation(),
1121                                               NTTP->getDeclName());
1122       if (TargetType.isNull())
1123         return ExprError();
1124
1125       return new (SemaRef.Context) SubstNonTypeTemplateParmPackExpr(TargetType,
1126                                                                     NTTP,
1127                                                               E->getLocation(),
1128                                                                     Arg);
1129     }
1130
1131     assert(getSema().ArgumentPackSubstitutionIndex < (int)Arg.pack_size());
1132     Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
1133   }
1134
1135   return transformNonTypeTemplateParmRef(NTTP, E->getLocation(), Arg);
1136 }
1137
1138 ExprResult TemplateInstantiator::transformNonTypeTemplateParmRef(
1139                                                  NonTypeTemplateParmDecl *parm,
1140                                                  SourceLocation loc,
1141                                                  const TemplateArgument &arg) {
1142   ExprResult result;
1143   QualType type;
1144
1145   // The template argument itself might be an expression, in which
1146   // case we just return that expression.
1147   if (arg.getKind() == TemplateArgument::Expression) {
1148     Expr *argExpr = arg.getAsExpr();
1149     result = SemaRef.Owned(argExpr);
1150     type = argExpr->getType();
1151
1152   } else if (arg.getKind() == TemplateArgument::Declaration) {
1153     ValueDecl *VD;
1154     if (Decl *D = arg.getAsDecl()) {
1155       VD = cast<ValueDecl>(D);
1156
1157       // Find the instantiation of the template argument.  This is
1158       // required for nested templates.
1159       VD = cast_or_null<ValueDecl>(
1160              getSema().FindInstantiatedDecl(loc, VD, TemplateArgs));
1161       if (!VD)
1162         return ExprError();
1163     } else {
1164       // Propagate NULL template argument.
1165       VD = 0;
1166     }
1167
1168     // Derive the type we want the substituted decl to have.  This had
1169     // better be non-dependent, or these checks will have serious problems.
1170     if (parm->isExpandedParameterPack()) {
1171       type = parm->getExpansionType(SemaRef.ArgumentPackSubstitutionIndex);
1172     } else if (parm->isParameterPack() &&
1173                isa<PackExpansionType>(parm->getType())) {
1174       type = SemaRef.SubstType(
1175                         cast<PackExpansionType>(parm->getType())->getPattern(),
1176                                      TemplateArgs, loc, parm->getDeclName());
1177     } else {
1178       type = SemaRef.SubstType(parm->getType(), TemplateArgs,
1179                                loc, parm->getDeclName());
1180     }
1181     assert(!type.isNull() && "type substitution failed for param type");
1182     assert(!type->isDependentType() && "param type still dependent");
1183     result = SemaRef.BuildExpressionFromDeclTemplateArgument(arg, type, loc);
1184
1185     if (!result.isInvalid()) type = result.get()->getType();
1186   } else {
1187     result = SemaRef.BuildExpressionFromIntegralTemplateArgument(arg, loc);
1188
1189     // Note that this type can be different from the type of 'result',
1190     // e.g. if it's an enum type.
1191     type = arg.getIntegralType();
1192   }
1193   if (result.isInvalid()) return ExprError();
1194
1195   Expr *resultExpr = result.take();
1196   return SemaRef.Owned(new (SemaRef.Context)
1197                 SubstNonTypeTemplateParmExpr(type,
1198                                              resultExpr->getValueKind(),
1199                                              loc, parm, resultExpr));
1200 }
1201
1202 ExprResult
1203 TemplateInstantiator::TransformSubstNonTypeTemplateParmPackExpr(
1204                                           SubstNonTypeTemplateParmPackExpr *E) {
1205   if (getSema().ArgumentPackSubstitutionIndex == -1) {
1206     // We aren't expanding the parameter pack, so just return ourselves.
1207     return getSema().Owned(E);
1208   }
1209
1210   const TemplateArgument &ArgPack = E->getArgumentPack();
1211   unsigned Index = (unsigned)getSema().ArgumentPackSubstitutionIndex;
1212   assert(Index < ArgPack.pack_size() && "Substitution index out-of-range");
1213
1214   const TemplateArgument &Arg = ArgPack.pack_begin()[Index];
1215   return transformNonTypeTemplateParmRef(E->getParameterPack(),
1216                                          E->getParameterPackLocation(),
1217                                          Arg);
1218 }
1219
1220 ExprResult
1221 TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E) {
1222   NamedDecl *D = E->getDecl();
1223   if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
1224     if (NTTP->getDepth() < TemplateArgs.getNumLevels())
1225       return TransformTemplateParmRefExpr(E, NTTP);
1226
1227     // We have a non-type template parameter that isn't fully substituted;
1228     // FindInstantiatedDecl will find it in the local instantiation scope.
1229   }
1230
1231   return TreeTransform<TemplateInstantiator>::TransformDeclRefExpr(E);
1232 }
1233
1234 ExprResult TemplateInstantiator::TransformCXXDefaultArgExpr(
1235     CXXDefaultArgExpr *E) {
1236   assert(!cast<FunctionDecl>(E->getParam()->getDeclContext())->
1237              getDescribedFunctionTemplate() &&
1238          "Default arg expressions are never formed in dependent cases.");
1239   return SemaRef.BuildCXXDefaultArgExpr(E->getUsedLocation(),
1240                            cast<FunctionDecl>(E->getParam()->getDeclContext()),
1241                                         E->getParam());
1242 }
1243
1244 QualType TemplateInstantiator::TransformFunctionProtoType(TypeLocBuilder &TLB,
1245                                                       FunctionProtoTypeLoc TL) {
1246   // We need a local instantiation scope for this function prototype.
1247   LocalInstantiationScope Scope(SemaRef, /*CombineWithOuterScope=*/true);
1248   return inherited::TransformFunctionProtoType(TLB, TL);
1249 }
1250
1251 QualType TemplateInstantiator::TransformFunctionProtoType(TypeLocBuilder &TLB,
1252                                  FunctionProtoTypeLoc TL,
1253                                  CXXRecordDecl *ThisContext,
1254                                  unsigned ThisTypeQuals) {
1255   // We need a local instantiation scope for this function prototype.
1256   LocalInstantiationScope Scope(SemaRef, /*CombineWithOuterScope=*/true);
1257   return inherited::TransformFunctionProtoType(TLB, TL, ThisContext,
1258                                                ThisTypeQuals);
1259 }
1260
1261 ParmVarDecl *
1262 TemplateInstantiator::TransformFunctionTypeParam(ParmVarDecl *OldParm,
1263                                                  int indexAdjustment,
1264                                        llvm::Optional<unsigned> NumExpansions,
1265                                                  bool ExpectParameterPack) {
1266   return SemaRef.SubstParmVarDecl(OldParm, TemplateArgs, indexAdjustment,
1267                                   NumExpansions, ExpectParameterPack);
1268 }
1269
1270 QualType
1271 TemplateInstantiator::TransformTemplateTypeParmType(TypeLocBuilder &TLB,
1272                                                 TemplateTypeParmTypeLoc TL) {
1273   const TemplateTypeParmType *T = TL.getTypePtr();
1274   if (T->getDepth() < TemplateArgs.getNumLevels()) {
1275     // Replace the template type parameter with its corresponding
1276     // template argument.
1277
1278     // If the corresponding template argument is NULL or doesn't exist, it's
1279     // because we are performing instantiation from explicitly-specified
1280     // template arguments in a function template class, but there were some
1281     // arguments left unspecified.
1282     if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex())) {
1283       TemplateTypeParmTypeLoc NewTL
1284         = TLB.push<TemplateTypeParmTypeLoc>(TL.getType());
1285       NewTL.setNameLoc(TL.getNameLoc());
1286       return TL.getType();
1287     }
1288
1289     TemplateArgument Arg = TemplateArgs(T->getDepth(), T->getIndex());
1290
1291     if (T->isParameterPack()) {
1292       assert(Arg.getKind() == TemplateArgument::Pack &&
1293              "Missing argument pack");
1294
1295       if (getSema().ArgumentPackSubstitutionIndex == -1) {
1296         // We have the template argument pack, but we're not expanding the
1297         // enclosing pack expansion yet. Just save the template argument
1298         // pack for later substitution.
1299         QualType Result
1300           = getSema().Context.getSubstTemplateTypeParmPackType(T, Arg);
1301         SubstTemplateTypeParmPackTypeLoc NewTL
1302           = TLB.push<SubstTemplateTypeParmPackTypeLoc>(Result);
1303         NewTL.setNameLoc(TL.getNameLoc());
1304         return Result;
1305       }
1306
1307       assert(getSema().ArgumentPackSubstitutionIndex < (int)Arg.pack_size());
1308       Arg = Arg.pack_begin()[getSema().ArgumentPackSubstitutionIndex];
1309     }
1310
1311     assert(Arg.getKind() == TemplateArgument::Type &&
1312            "Template argument kind mismatch");
1313
1314     QualType Replacement = Arg.getAsType();
1315
1316     // TODO: only do this uniquing once, at the start of instantiation.
1317     QualType Result
1318       = getSema().Context.getSubstTemplateTypeParmType(T, Replacement);
1319     SubstTemplateTypeParmTypeLoc NewTL
1320       = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
1321     NewTL.setNameLoc(TL.getNameLoc());
1322     return Result;
1323   }
1324
1325   // The template type parameter comes from an inner template (e.g.,
1326   // the template parameter list of a member template inside the
1327   // template we are instantiating). Create a new template type
1328   // parameter with the template "level" reduced by one.
1329   TemplateTypeParmDecl *NewTTPDecl = 0;
1330   if (TemplateTypeParmDecl *OldTTPDecl = T->getDecl())
1331     NewTTPDecl = cast_or_null<TemplateTypeParmDecl>(
1332                                   TransformDecl(TL.getNameLoc(), OldTTPDecl));
1333
1334   QualType Result
1335     = getSema().Context.getTemplateTypeParmType(T->getDepth()
1336                                                  - TemplateArgs.getNumLevels(),
1337                                                 T->getIndex(),
1338                                                 T->isParameterPack(),
1339                                                 NewTTPDecl);
1340   TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
1341   NewTL.setNameLoc(TL.getNameLoc());
1342   return Result;
1343 }
1344
1345 QualType
1346 TemplateInstantiator::TransformSubstTemplateTypeParmPackType(
1347                                                             TypeLocBuilder &TLB,
1348                                          SubstTemplateTypeParmPackTypeLoc TL) {
1349   if (getSema().ArgumentPackSubstitutionIndex == -1) {
1350     // We aren't expanding the parameter pack, so just return ourselves.
1351     SubstTemplateTypeParmPackTypeLoc NewTL
1352       = TLB.push<SubstTemplateTypeParmPackTypeLoc>(TL.getType());
1353     NewTL.setNameLoc(TL.getNameLoc());
1354     return TL.getType();
1355   }
1356
1357   const TemplateArgument &ArgPack = TL.getTypePtr()->getArgumentPack();
1358   unsigned Index = (unsigned)getSema().ArgumentPackSubstitutionIndex;
1359   assert(Index < ArgPack.pack_size() && "Substitution index out-of-range");
1360
1361   QualType Result = ArgPack.pack_begin()[Index].getAsType();
1362   Result = getSema().Context.getSubstTemplateTypeParmType(
1363                                       TL.getTypePtr()->getReplacedParameter(),
1364                                                           Result);
1365   SubstTemplateTypeParmTypeLoc NewTL
1366     = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
1367   NewTL.setNameLoc(TL.getNameLoc());
1368   return Result;
1369 }
1370
1371 /// \brief Perform substitution on the type T with a given set of template
1372 /// arguments.
1373 ///
1374 /// This routine substitutes the given template arguments into the
1375 /// type T and produces the instantiated type.
1376 ///
1377 /// \param T the type into which the template arguments will be
1378 /// substituted. If this type is not dependent, it will be returned
1379 /// immediately.
1380 ///
1381 /// \param TemplateArgs the template arguments that will be
1382 /// substituted for the top-level template parameters within T.
1383 ///
1384 /// \param Loc the location in the source code where this substitution
1385 /// is being performed. It will typically be the location of the
1386 /// declarator (if we're instantiating the type of some declaration)
1387 /// or the location of the type in the source code (if, e.g., we're
1388 /// instantiating the type of a cast expression).
1389 ///
1390 /// \param Entity the name of the entity associated with a declaration
1391 /// being instantiated (if any). May be empty to indicate that there
1392 /// is no such entity (if, e.g., this is a type that occurs as part of
1393 /// a cast expression) or that the entity has no name (e.g., an
1394 /// unnamed function parameter).
1395 ///
1396 /// \returns If the instantiation succeeds, the instantiated
1397 /// type. Otherwise, produces diagnostics and returns a NULL type.
1398 TypeSourceInfo *Sema::SubstType(TypeSourceInfo *T,
1399                                 const MultiLevelTemplateArgumentList &Args,
1400                                 SourceLocation Loc,
1401                                 DeclarationName Entity) {
1402   assert(!ActiveTemplateInstantiations.empty() &&
1403          "Cannot perform an instantiation without some context on the "
1404          "instantiation stack");
1405
1406   if (!T->getType()->isInstantiationDependentType() &&
1407       !T->getType()->isVariablyModifiedType())
1408     return T;
1409
1410   TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1411   return Instantiator.TransformType(T);
1412 }
1413
1414 TypeSourceInfo *Sema::SubstType(TypeLoc TL,
1415                                 const MultiLevelTemplateArgumentList &Args,
1416                                 SourceLocation Loc,
1417                                 DeclarationName Entity) {
1418   assert(!ActiveTemplateInstantiations.empty() &&
1419          "Cannot perform an instantiation without some context on the "
1420          "instantiation stack");
1421
1422   if (TL.getType().isNull())
1423     return 0;
1424
1425   if (!TL.getType()->isInstantiationDependentType() &&
1426       !TL.getType()->isVariablyModifiedType()) {
1427     // FIXME: Make a copy of the TypeLoc data here, so that we can
1428     // return a new TypeSourceInfo. Inefficient!
1429     TypeLocBuilder TLB;
1430     TLB.pushFullCopy(TL);
1431     return TLB.getTypeSourceInfo(Context, TL.getType());
1432   }
1433
1434   TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1435   TypeLocBuilder TLB;
1436   TLB.reserve(TL.getFullDataSize());
1437   QualType Result = Instantiator.TransformType(TLB, TL);
1438   if (Result.isNull())
1439     return 0;
1440
1441   return TLB.getTypeSourceInfo(Context, Result);
1442 }
1443
1444 /// Deprecated form of the above.
1445 QualType Sema::SubstType(QualType T,
1446                          const MultiLevelTemplateArgumentList &TemplateArgs,
1447                          SourceLocation Loc, DeclarationName Entity) {
1448   assert(!ActiveTemplateInstantiations.empty() &&
1449          "Cannot perform an instantiation without some context on the "
1450          "instantiation stack");
1451
1452   // If T is not a dependent type or a variably-modified type, there
1453   // is nothing to do.
1454   if (!T->isInstantiationDependentType() && !T->isVariablyModifiedType())
1455     return T;
1456
1457   TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
1458   return Instantiator.TransformType(T);
1459 }
1460
1461 static bool NeedsInstantiationAsFunctionType(TypeSourceInfo *T) {
1462   if (T->getType()->isInstantiationDependentType() ||
1463       T->getType()->isVariablyModifiedType())
1464     return true;
1465
1466   TypeLoc TL = T->getTypeLoc().IgnoreParens();
1467   if (!isa<FunctionProtoTypeLoc>(TL))
1468     return false;
1469
1470   FunctionProtoTypeLoc FP = cast<FunctionProtoTypeLoc>(TL);
1471   for (unsigned I = 0, E = FP.getNumArgs(); I != E; ++I) {
1472     ParmVarDecl *P = FP.getArg(I);
1473
1474     // The parameter's type as written might be dependent even if the
1475     // decayed type was not dependent.
1476     if (TypeSourceInfo *TSInfo = P->getTypeSourceInfo())
1477       if (TSInfo->getType()->isInstantiationDependentType())
1478         return true;
1479
1480     // TODO: currently we always rebuild expressions.  When we
1481     // properly get lazier about this, we should use the same
1482     // logic to avoid rebuilding prototypes here.
1483     if (P->hasDefaultArg())
1484       return true;
1485   }
1486
1487   return false;
1488 }
1489
1490 /// A form of SubstType intended specifically for instantiating the
1491 /// type of a FunctionDecl.  Its purpose is solely to force the
1492 /// instantiation of default-argument expressions.
1493 TypeSourceInfo *Sema::SubstFunctionDeclType(TypeSourceInfo *T,
1494                                 const MultiLevelTemplateArgumentList &Args,
1495                                 SourceLocation Loc,
1496                                 DeclarationName Entity,
1497                                 CXXRecordDecl *ThisContext,
1498                                 unsigned ThisTypeQuals) {
1499   assert(!ActiveTemplateInstantiations.empty() &&
1500          "Cannot perform an instantiation without some context on the "
1501          "instantiation stack");
1502
1503   if (!NeedsInstantiationAsFunctionType(T))
1504     return T;
1505
1506   TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1507
1508   TypeLocBuilder TLB;
1509
1510   TypeLoc TL = T->getTypeLoc();
1511   TLB.reserve(TL.getFullDataSize());
1512
1513   QualType Result;
1514
1515   if (FunctionProtoTypeLoc *Proto = dyn_cast<FunctionProtoTypeLoc>(&TL)) {
1516     Result = Instantiator.TransformFunctionProtoType(TLB, *Proto, ThisContext,
1517                                                      ThisTypeQuals);
1518   } else {
1519     Result = Instantiator.TransformType(TLB, TL);
1520   }
1521   if (Result.isNull())
1522     return 0;
1523
1524   return TLB.getTypeSourceInfo(Context, Result);
1525 }
1526
1527 ParmVarDecl *Sema::SubstParmVarDecl(ParmVarDecl *OldParm,
1528                             const MultiLevelTemplateArgumentList &TemplateArgs,
1529                                     int indexAdjustment,
1530                                     llvm::Optional<unsigned> NumExpansions,
1531                                     bool ExpectParameterPack) {
1532   TypeSourceInfo *OldDI = OldParm->getTypeSourceInfo();
1533   TypeSourceInfo *NewDI = 0;
1534
1535   TypeLoc OldTL = OldDI->getTypeLoc();
1536   if (isa<PackExpansionTypeLoc>(OldTL)) {
1537     PackExpansionTypeLoc ExpansionTL = cast<PackExpansionTypeLoc>(OldTL);
1538
1539     // We have a function parameter pack. Substitute into the pattern of the
1540     // expansion.
1541     NewDI = SubstType(ExpansionTL.getPatternLoc(), TemplateArgs,
1542                       OldParm->getLocation(), OldParm->getDeclName());
1543     if (!NewDI)
1544       return 0;
1545
1546     if (NewDI->getType()->containsUnexpandedParameterPack()) {
1547       // We still have unexpanded parameter packs, which means that
1548       // our function parameter is still a function parameter pack.
1549       // Therefore, make its type a pack expansion type.
1550       NewDI = CheckPackExpansion(NewDI, ExpansionTL.getEllipsisLoc(),
1551                                  NumExpansions);
1552     } else if (ExpectParameterPack) {
1553       // We expected to get a parameter pack but didn't (because the type
1554       // itself is not a pack expansion type), so complain. This can occur when
1555       // the substitution goes through an alias template that "loses" the
1556       // pack expansion.
1557       Diag(OldParm->getLocation(),
1558            diag::err_function_parameter_pack_without_parameter_packs)
1559         << NewDI->getType();
1560       return 0;
1561     }
1562   } else {
1563     NewDI = SubstType(OldDI, TemplateArgs, OldParm->getLocation(),
1564                       OldParm->getDeclName());
1565   }
1566
1567   if (!NewDI)
1568     return 0;
1569
1570   if (NewDI->getType()->isVoidType()) {
1571     Diag(OldParm->getLocation(), diag::err_param_with_void_type);
1572     return 0;
1573   }
1574
1575   ParmVarDecl *NewParm = CheckParameter(Context.getTranslationUnitDecl(),
1576                                         OldParm->getInnerLocStart(),
1577                                         OldParm->getLocation(),
1578                                         OldParm->getIdentifier(),
1579                                         NewDI->getType(), NewDI,
1580                                         OldParm->getStorageClass(),
1581                                         OldParm->getStorageClassAsWritten());
1582   if (!NewParm)
1583     return 0;
1584
1585   // Mark the (new) default argument as uninstantiated (if any).
1586   if (OldParm->hasUninstantiatedDefaultArg()) {
1587     Expr *Arg = OldParm->getUninstantiatedDefaultArg();
1588     NewParm->setUninstantiatedDefaultArg(Arg);
1589   } else if (OldParm->hasUnparsedDefaultArg()) {
1590     NewParm->setUnparsedDefaultArg();
1591     UnparsedDefaultArgInstantiations[OldParm].push_back(NewParm);
1592   } else if (Expr *Arg = OldParm->getDefaultArg())
1593     NewParm->setUninstantiatedDefaultArg(Arg);
1594
1595   NewParm->setHasInheritedDefaultArg(OldParm->hasInheritedDefaultArg());
1596
1597   if (OldParm->isParameterPack() && !NewParm->isParameterPack()) {
1598     // Add the new parameter to the instantiated parameter pack.
1599     CurrentInstantiationScope->InstantiatedLocalPackArg(OldParm, NewParm);
1600   } else {
1601     // Introduce an Old -> New mapping
1602     CurrentInstantiationScope->InstantiatedLocal(OldParm, NewParm);
1603   }
1604
1605   // FIXME: OldParm may come from a FunctionProtoType, in which case CurContext
1606   // can be anything, is this right ?
1607   NewParm->setDeclContext(CurContext);
1608
1609   NewParm->setScopeInfo(OldParm->getFunctionScopeDepth(),
1610                         OldParm->getFunctionScopeIndex() + indexAdjustment);
1611
1612   return NewParm;
1613 }
1614
1615 /// \brief Substitute the given template arguments into the given set of
1616 /// parameters, producing the set of parameter types that would be generated
1617 /// from such a substitution.
1618 bool Sema::SubstParmTypes(SourceLocation Loc,
1619                           ParmVarDecl **Params, unsigned NumParams,
1620                           const MultiLevelTemplateArgumentList &TemplateArgs,
1621                           SmallVectorImpl<QualType> &ParamTypes,
1622                           SmallVectorImpl<ParmVarDecl *> *OutParams) {
1623   assert(!ActiveTemplateInstantiations.empty() &&
1624          "Cannot perform an instantiation without some context on the "
1625          "instantiation stack");
1626
1627   TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
1628                                     DeclarationName());
1629   return Instantiator.TransformFunctionTypeParams(Loc, Params, NumParams, 0,
1630                                                   ParamTypes, OutParams);
1631 }
1632
1633 /// \brief Perform substitution on the base class specifiers of the
1634 /// given class template specialization.
1635 ///
1636 /// Produces a diagnostic and returns true on error, returns false and
1637 /// attaches the instantiated base classes to the class template
1638 /// specialization if successful.
1639 bool
1640 Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
1641                           CXXRecordDecl *Pattern,
1642                           const MultiLevelTemplateArgumentList &TemplateArgs) {
1643   bool Invalid = false;
1644   SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
1645   for (ClassTemplateSpecializationDecl::base_class_iterator
1646          Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
1647        Base != BaseEnd; ++Base) {
1648     if (!Base->getType()->isDependentType()) {
1649       InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(*Base));
1650       continue;
1651     }
1652
1653     SourceLocation EllipsisLoc;
1654     TypeSourceInfo *BaseTypeLoc;
1655     if (Base->isPackExpansion()) {
1656       // This is a pack expansion. See whether we should expand it now, or
1657       // wait until later.
1658       SmallVector<UnexpandedParameterPack, 2> Unexpanded;
1659       collectUnexpandedParameterPacks(Base->getTypeSourceInfo()->getTypeLoc(),
1660                                       Unexpanded);
1661       bool ShouldExpand = false;
1662       bool RetainExpansion = false;
1663       llvm::Optional<unsigned> NumExpansions;
1664       if (CheckParameterPacksForExpansion(Base->getEllipsisLoc(),
1665                                           Base->getSourceRange(),
1666                                           Unexpanded,
1667                                           TemplateArgs, ShouldExpand,
1668                                           RetainExpansion,
1669                                           NumExpansions)) {
1670         Invalid = true;
1671         continue;
1672       }
1673
1674       // If we should expand this pack expansion now, do so.
1675       if (ShouldExpand) {
1676         for (unsigned I = 0; I != *NumExpansions; ++I) {
1677             Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(*this, I);
1678
1679           TypeSourceInfo *BaseTypeLoc = SubstType(Base->getTypeSourceInfo(),
1680                                                   TemplateArgs,
1681                                               Base->getSourceRange().getBegin(),
1682                                                   DeclarationName());
1683           if (!BaseTypeLoc) {
1684             Invalid = true;
1685             continue;
1686           }
1687
1688           if (CXXBaseSpecifier *InstantiatedBase
1689                 = CheckBaseSpecifier(Instantiation,
1690                                      Base->getSourceRange(),
1691                                      Base->isVirtual(),
1692                                      Base->getAccessSpecifierAsWritten(),
1693                                      BaseTypeLoc,
1694                                      SourceLocation()))
1695             InstantiatedBases.push_back(InstantiatedBase);
1696           else
1697             Invalid = true;
1698         }
1699
1700         continue;
1701       }
1702
1703       // The resulting base specifier will (still) be a pack expansion.
1704       EllipsisLoc = Base->getEllipsisLoc();
1705       Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(*this, -1);
1706       BaseTypeLoc = SubstType(Base->getTypeSourceInfo(),
1707                               TemplateArgs,
1708                               Base->getSourceRange().getBegin(),
1709                               DeclarationName());
1710     } else {
1711       BaseTypeLoc = SubstType(Base->getTypeSourceInfo(),
1712                               TemplateArgs,
1713                               Base->getSourceRange().getBegin(),
1714                               DeclarationName());
1715     }
1716
1717     if (!BaseTypeLoc) {
1718       Invalid = true;
1719       continue;
1720     }
1721
1722     if (CXXBaseSpecifier *InstantiatedBase
1723           = CheckBaseSpecifier(Instantiation,
1724                                Base->getSourceRange(),
1725                                Base->isVirtual(),
1726                                Base->getAccessSpecifierAsWritten(),
1727                                BaseTypeLoc,
1728                                EllipsisLoc))
1729       InstantiatedBases.push_back(InstantiatedBase);
1730     else
1731       Invalid = true;
1732   }
1733
1734   if (!Invalid &&
1735       AttachBaseSpecifiers(Instantiation, InstantiatedBases.data(),
1736                            InstantiatedBases.size()))
1737     Invalid = true;
1738
1739   return Invalid;
1740 }
1741
1742 // Defined via #include from SemaTemplateInstantiateDecl.cpp
1743 namespace clang {
1744   namespace sema {
1745     Attr *instantiateTemplateAttribute(const Attr *At, ASTContext &C, Sema &S,
1746                             const MultiLevelTemplateArgumentList &TemplateArgs);
1747   }
1748 }
1749
1750 /// Determine whether we would be unable to instantiate this template (because
1751 /// it either has no definition, or is in the process of being instantiated).
1752 static bool DiagnoseUninstantiableTemplate(Sema &S,
1753                                            SourceLocation PointOfInstantiation,
1754                                            TagDecl *Instantiation,
1755                                            bool InstantiatedFromMember,
1756                                            TagDecl *Pattern,
1757                                            TagDecl *PatternDef,
1758                                            TemplateSpecializationKind TSK,
1759                                            bool Complain = true) {
1760   if (PatternDef && !PatternDef->isBeingDefined())
1761     return false;
1762
1763   if (!Complain || (PatternDef && PatternDef->isInvalidDecl())) {
1764     // Say nothing
1765   } else if (PatternDef) {
1766     assert(PatternDef->isBeingDefined());
1767     S.Diag(PointOfInstantiation,
1768            diag::err_template_instantiate_within_definition)
1769       << (TSK != TSK_ImplicitInstantiation)
1770       << S.Context.getTypeDeclType(Instantiation);
1771     // Not much point in noting the template declaration here, since
1772     // we're lexically inside it.
1773     Instantiation->setInvalidDecl();
1774   } else if (InstantiatedFromMember) {
1775     S.Diag(PointOfInstantiation,
1776            diag::err_implicit_instantiate_member_undefined)
1777       << S.Context.getTypeDeclType(Instantiation);
1778     S.Diag(Pattern->getLocation(), diag::note_member_of_template_here);
1779   } else {
1780     S.Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
1781       << (TSK != TSK_ImplicitInstantiation)
1782       << S.Context.getTypeDeclType(Instantiation);
1783     S.Diag(Pattern->getLocation(), diag::note_template_decl_here);
1784   }
1785
1786   // In general, Instantiation isn't marked invalid to get more than one
1787   // error for multiple undefined instantiations. But the code that does
1788   // explicit declaration -> explicit definition conversion can't handle
1789   // invalid declarations, so mark as invalid in that case.
1790   if (TSK == TSK_ExplicitInstantiationDeclaration)
1791     Instantiation->setInvalidDecl();
1792   return true;
1793 }
1794
1795 /// \brief Instantiate the definition of a class from a given pattern.
1796 ///
1797 /// \param PointOfInstantiation The point of instantiation within the
1798 /// source code.
1799 ///
1800 /// \param Instantiation is the declaration whose definition is being
1801 /// instantiated. This will be either a class template specialization
1802 /// or a member class of a class template specialization.
1803 ///
1804 /// \param Pattern is the pattern from which the instantiation
1805 /// occurs. This will be either the declaration of a class template or
1806 /// the declaration of a member class of a class template.
1807 ///
1808 /// \param TemplateArgs The template arguments to be substituted into
1809 /// the pattern.
1810 ///
1811 /// \param TSK the kind of implicit or explicit instantiation to perform.
1812 ///
1813 /// \param Complain whether to complain if the class cannot be instantiated due
1814 /// to the lack of a definition.
1815 ///
1816 /// \returns true if an error occurred, false otherwise.
1817 bool
1818 Sema::InstantiateClass(SourceLocation PointOfInstantiation,
1819                        CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
1820                        const MultiLevelTemplateArgumentList &TemplateArgs,
1821                        TemplateSpecializationKind TSK,
1822                        bool Complain) {
1823   bool Invalid = false;
1824
1825   CXXRecordDecl *PatternDef
1826     = cast_or_null<CXXRecordDecl>(Pattern->getDefinition());
1827   if (DiagnoseUninstantiableTemplate(*this, PointOfInstantiation, Instantiation,
1828                                 Instantiation->getInstantiatedFromMemberClass(),
1829                                      Pattern, PatternDef, TSK, Complain))
1830     return true;
1831   Pattern = PatternDef;
1832
1833   // \brief Record the point of instantiation.
1834   if (MemberSpecializationInfo *MSInfo
1835         = Instantiation->getMemberSpecializationInfo()) {
1836     MSInfo->setTemplateSpecializationKind(TSK);
1837     MSInfo->setPointOfInstantiation(PointOfInstantiation);
1838   } else if (ClassTemplateSpecializationDecl *Spec
1839         = dyn_cast<ClassTemplateSpecializationDecl>(Instantiation)) {
1840     Spec->setTemplateSpecializationKind(TSK);
1841     Spec->setPointOfInstantiation(PointOfInstantiation);
1842   }
1843
1844   InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
1845   if (Inst)
1846     return true;
1847
1848   // Enter the scope of this instantiation. We don't use
1849   // PushDeclContext because we don't have a scope.
1850   ContextRAII SavedContext(*this, Instantiation);
1851   EnterExpressionEvaluationContext EvalContext(*this,
1852                                                Sema::PotentiallyEvaluated);
1853
1854   // If this is an instantiation of a local class, merge this local
1855   // instantiation scope with the enclosing scope. Otherwise, every
1856   // instantiation of a class has its own local instantiation scope.
1857   bool MergeWithParentScope = !Instantiation->isDefinedOutsideFunctionOrMethod();
1858   LocalInstantiationScope Scope(*this, MergeWithParentScope);
1859
1860   // Pull attributes from the pattern onto the instantiation.
1861   InstantiateAttrs(TemplateArgs, Pattern, Instantiation);
1862
1863   // Start the definition of this instantiation.
1864   Instantiation->startDefinition();
1865
1866   Instantiation->setTagKind(Pattern->getTagKind());
1867
1868   // Do substitution on the base class specifiers.
1869   if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
1870     Invalid = true;
1871
1872   TemplateDeclInstantiator Instantiator(*this, Instantiation, TemplateArgs);
1873   SmallVector<Decl*, 4> Fields;
1874   SmallVector<std::pair<FieldDecl*, FieldDecl*>, 4>
1875     FieldsWithMemberInitializers;
1876   // Delay instantiation of late parsed attributes.
1877   LateInstantiatedAttrVec LateAttrs;
1878   Instantiator.enableLateAttributeInstantiation(&LateAttrs);
1879
1880   for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
1881          MemberEnd = Pattern->decls_end();
1882        Member != MemberEnd; ++Member) {
1883     // Don't instantiate members not belonging in this semantic context.
1884     // e.g. for:
1885     // @code
1886     //    template <int i> class A {
1887     //      class B *g;
1888     //    };
1889     // @endcode
1890     // 'class B' has the template as lexical context but semantically it is
1891     // introduced in namespace scope.
1892     if ((*Member)->getDeclContext() != Pattern)
1893       continue;
1894
1895     if ((*Member)->isInvalidDecl()) {
1896       Invalid = true;
1897       continue;
1898     }
1899
1900     Decl *NewMember = Instantiator.Visit(*Member);
1901     if (NewMember) {
1902       if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember)) {
1903         Fields.push_back(Field);
1904         FieldDecl *OldField = cast<FieldDecl>(*Member);
1905         if (OldField->getInClassInitializer())
1906           FieldsWithMemberInitializers.push_back(std::make_pair(OldField,
1907                                                                 Field));
1908       } else if (EnumDecl *Enum = dyn_cast<EnumDecl>(NewMember)) {
1909         // C++11 [temp.inst]p1: The implicit instantiation of a class template
1910         // specialization causes the implicit instantiation of the definitions
1911         // of unscoped member enumerations.
1912         // Record a point of instantiation for this implicit instantiation.
1913         if (TSK == TSK_ImplicitInstantiation && !Enum->isScoped() &&
1914             Enum->isCompleteDefinition()) {
1915           MemberSpecializationInfo *MSInfo =Enum->getMemberSpecializationInfo();
1916           assert(MSInfo && "no spec info for member enum specialization");
1917           MSInfo->setTemplateSpecializationKind(TSK_ImplicitInstantiation);
1918           MSInfo->setPointOfInstantiation(PointOfInstantiation);
1919         }
1920       }
1921
1922       if (NewMember->isInvalidDecl())
1923         Invalid = true;
1924     } else {
1925       // FIXME: Eventually, a NULL return will mean that one of the
1926       // instantiations was a semantic disaster, and we'll want to set Invalid =
1927       // true. For now, we expect to skip some members that we can't yet handle.
1928     }
1929   }
1930
1931   // Finish checking fields.
1932   ActOnFields(0, Instantiation->getLocation(), Instantiation, Fields,
1933               SourceLocation(), SourceLocation(), 0);
1934   CheckCompletedCXXClass(Instantiation);
1935
1936   // Attach any in-class member initializers now the class is complete.
1937   {
1938     // C++11 [expr.prim.general]p4:
1939     //   Otherwise, if a member-declarator declares a non-static data member
1940     //  (9.2) of a class X, the expression this is a prvalue of type "pointer
1941     //  to X" within the optional brace-or-equal-initializer. It shall not
1942     //  appear elsewhere in the member-declarator.
1943     CXXThisScopeRAII ThisScope(*this, Instantiation, (unsigned)0);
1944
1945     for (unsigned I = 0, N = FieldsWithMemberInitializers.size(); I != N; ++I) {
1946       FieldDecl *OldField = FieldsWithMemberInitializers[I].first;
1947       FieldDecl *NewField = FieldsWithMemberInitializers[I].second;
1948       Expr *OldInit = OldField->getInClassInitializer();
1949
1950       ExprResult NewInit = SubstInitializer(OldInit, TemplateArgs,
1951                                             /*CXXDirectInit=*/false);
1952       if (NewInit.isInvalid())
1953         NewField->setInvalidDecl();
1954       else {
1955         Expr *Init = NewInit.take();
1956         assert(Init && "no-argument initializer in class");
1957         assert(!isa<ParenListExpr>(Init) && "call-style init in class");
1958         ActOnCXXInClassMemberInitializer(NewField,
1959                                          Init->getSourceRange().getBegin(),
1960                                          Init);
1961       }
1962     }
1963   }
1964   // Instantiate late parsed attributes, and attach them to their decls.
1965   // See Sema::InstantiateAttrs
1966   for (LateInstantiatedAttrVec::iterator I = LateAttrs.begin(),
1967        E = LateAttrs.end(); I != E; ++I) {
1968     assert(CurrentInstantiationScope == Instantiator.getStartingScope());
1969     CurrentInstantiationScope = I->Scope;
1970     Attr *NewAttr =
1971       instantiateTemplateAttribute(I->TmplAttr, Context, *this, TemplateArgs);
1972     I->NewDecl->addAttr(NewAttr);
1973     LocalInstantiationScope::deleteScopes(I->Scope,
1974                                           Instantiator.getStartingScope());
1975   }
1976   Instantiator.disableLateAttributeInstantiation();
1977   LateAttrs.clear();
1978
1979   if (!FieldsWithMemberInitializers.empty())
1980     ActOnFinishDelayedMemberInitializers(Instantiation);
1981
1982   if (TSK == TSK_ImplicitInstantiation) {
1983     Instantiation->setLocation(Pattern->getLocation());
1984     Instantiation->setLocStart(Pattern->getInnerLocStart());
1985     Instantiation->setRBraceLoc(Pattern->getRBraceLoc());
1986   }
1987
1988   if (Instantiation->isInvalidDecl())
1989     Invalid = true;
1990   else {
1991     // Instantiate any out-of-line class template partial
1992     // specializations now.
1993     for (TemplateDeclInstantiator::delayed_partial_spec_iterator
1994               P = Instantiator.delayed_partial_spec_begin(),
1995            PEnd = Instantiator.delayed_partial_spec_end();
1996          P != PEnd; ++P) {
1997       if (!Instantiator.InstantiateClassTemplatePartialSpecialization(
1998                                                                 P->first,
1999                                                                 P->second)) {
2000         Invalid = true;
2001         break;
2002       }
2003     }
2004   }
2005
2006   // Exit the scope of this instantiation.
2007   SavedContext.pop();
2008
2009   if (!Invalid) {
2010     Consumer.HandleTagDeclDefinition(Instantiation);
2011
2012     // Always emit the vtable for an explicit instantiation definition
2013     // of a polymorphic class template specialization.
2014     if (TSK == TSK_ExplicitInstantiationDefinition)
2015       MarkVTableUsed(PointOfInstantiation, Instantiation, true);
2016   }
2017
2018   return Invalid;
2019 }
2020
2021 /// \brief Instantiate the definition of an enum from a given pattern.
2022 ///
2023 /// \param PointOfInstantiation The point of instantiation within the
2024 ///        source code.
2025 /// \param Instantiation is the declaration whose definition is being
2026 ///        instantiated. This will be a member enumeration of a class
2027 ///        temploid specialization, or a local enumeration within a
2028 ///        function temploid specialization.
2029 /// \param Pattern The templated declaration from which the instantiation
2030 ///        occurs.
2031 /// \param TemplateArgs The template arguments to be substituted into
2032 ///        the pattern.
2033 /// \param TSK The kind of implicit or explicit instantiation to perform.
2034 ///
2035 /// \return \c true if an error occurred, \c false otherwise.
2036 bool Sema::InstantiateEnum(SourceLocation PointOfInstantiation,
2037                            EnumDecl *Instantiation, EnumDecl *Pattern,
2038                            const MultiLevelTemplateArgumentList &TemplateArgs,
2039                            TemplateSpecializationKind TSK) {
2040   EnumDecl *PatternDef = Pattern->getDefinition();
2041   if (DiagnoseUninstantiableTemplate(*this, PointOfInstantiation, Instantiation,
2042                                  Instantiation->getInstantiatedFromMemberEnum(),
2043                                      Pattern, PatternDef, TSK,/*Complain*/true))
2044     return true;
2045   Pattern = PatternDef;
2046
2047   // Record the point of instantiation.
2048   if (MemberSpecializationInfo *MSInfo
2049         = Instantiation->getMemberSpecializationInfo()) {
2050     MSInfo->setTemplateSpecializationKind(TSK);
2051     MSInfo->setPointOfInstantiation(PointOfInstantiation);
2052   }
2053
2054   InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
2055   if (Inst)
2056     return true;
2057
2058   // Enter the scope of this instantiation. We don't use
2059   // PushDeclContext because we don't have a scope.
2060   ContextRAII SavedContext(*this, Instantiation);
2061   EnterExpressionEvaluationContext EvalContext(*this,
2062                                                Sema::PotentiallyEvaluated);
2063
2064   LocalInstantiationScope Scope(*this, /*MergeWithParentScope*/true);
2065
2066   // Pull attributes from the pattern onto the instantiation.
2067   InstantiateAttrs(TemplateArgs, Pattern, Instantiation);
2068
2069   TemplateDeclInstantiator Instantiator(*this, Instantiation, TemplateArgs);
2070   Instantiator.InstantiateEnumDefinition(Instantiation, Pattern);
2071
2072   // Exit the scope of this instantiation.
2073   SavedContext.pop();
2074
2075   return Instantiation->isInvalidDecl();
2076 }
2077
2078 namespace {
2079   /// \brief A partial specialization whose template arguments have matched
2080   /// a given template-id.
2081   struct PartialSpecMatchResult {
2082     ClassTemplatePartialSpecializationDecl *Partial;
2083     TemplateArgumentList *Args;
2084   };
2085 }
2086
2087 bool
2088 Sema::InstantiateClassTemplateSpecialization(
2089                            SourceLocation PointOfInstantiation,
2090                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
2091                            TemplateSpecializationKind TSK,
2092                            bool Complain) {
2093   // Perform the actual instantiation on the canonical declaration.
2094   ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
2095                                          ClassTemplateSpec->getCanonicalDecl());
2096
2097   // Check whether we have already instantiated or specialized this class
2098   // template specialization.
2099   if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared) {
2100     if (ClassTemplateSpec->getSpecializationKind() ==
2101           TSK_ExplicitInstantiationDeclaration &&
2102         TSK == TSK_ExplicitInstantiationDefinition) {
2103       // An explicit instantiation definition follows an explicit instantiation
2104       // declaration (C++0x [temp.explicit]p10); go ahead and perform the
2105       // explicit instantiation.
2106       ClassTemplateSpec->setSpecializationKind(TSK);
2107
2108       // If this is an explicit instantiation definition, mark the
2109       // vtable as used.
2110       if (TSK == TSK_ExplicitInstantiationDefinition &&
2111           !ClassTemplateSpec->isInvalidDecl())
2112         MarkVTableUsed(PointOfInstantiation, ClassTemplateSpec, true);
2113
2114       return false;
2115     }
2116
2117     // We can only instantiate something that hasn't already been
2118     // instantiated or specialized. Fail without any diagnostics: our
2119     // caller will provide an error message.
2120     return true;
2121   }
2122
2123   if (ClassTemplateSpec->isInvalidDecl())
2124     return true;
2125
2126   ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
2127   CXXRecordDecl *Pattern = 0;
2128
2129   // C++ [temp.class.spec.match]p1:
2130   //   When a class template is used in a context that requires an
2131   //   instantiation of the class, it is necessary to determine
2132   //   whether the instantiation is to be generated using the primary
2133   //   template or one of the partial specializations. This is done by
2134   //   matching the template arguments of the class template
2135   //   specialization with the template argument lists of the partial
2136   //   specializations.
2137   typedef PartialSpecMatchResult MatchResult;
2138   SmallVector<MatchResult, 4> Matched;
2139   SmallVector<ClassTemplatePartialSpecializationDecl *, 4> PartialSpecs;
2140   Template->getPartialSpecializations(PartialSpecs);
2141   for (unsigned I = 0, N = PartialSpecs.size(); I != N; ++I) {
2142     ClassTemplatePartialSpecializationDecl *Partial = PartialSpecs[I];
2143     TemplateDeductionInfo Info(Context, PointOfInstantiation);
2144     if (TemplateDeductionResult Result
2145           = DeduceTemplateArguments(Partial,
2146                                     ClassTemplateSpec->getTemplateArgs(),
2147                                     Info)) {
2148       // FIXME: Store the failed-deduction information for use in
2149       // diagnostics, later.
2150       (void)Result;
2151     } else {
2152       Matched.push_back(PartialSpecMatchResult());
2153       Matched.back().Partial = Partial;
2154       Matched.back().Args = Info.take();
2155     }
2156   }
2157
2158   // If we're dealing with a member template where the template parameters
2159   // have been instantiated, this provides the original template parameters
2160   // from which the member template's parameters were instantiated.
2161   SmallVector<const NamedDecl *, 4> InstantiatedTemplateParameters;
2162
2163   if (Matched.size() >= 1) {
2164     SmallVector<MatchResult, 4>::iterator Best = Matched.begin();
2165     if (Matched.size() == 1) {
2166       //   -- If exactly one matching specialization is found, the
2167       //      instantiation is generated from that specialization.
2168       // We don't need to do anything for this.
2169     } else {
2170       //   -- If more than one matching specialization is found, the
2171       //      partial order rules (14.5.4.2) are used to determine
2172       //      whether one of the specializations is more specialized
2173       //      than the others. If none of the specializations is more
2174       //      specialized than all of the other matching
2175       //      specializations, then the use of the class template is
2176       //      ambiguous and the program is ill-formed.
2177       for (SmallVector<MatchResult, 4>::iterator P = Best + 1,
2178                                                     PEnd = Matched.end();
2179            P != PEnd; ++P) {
2180         if (getMoreSpecializedPartialSpecialization(P->Partial, Best->Partial,
2181                                                     PointOfInstantiation)
2182               == P->Partial)
2183           Best = P;
2184       }
2185
2186       // Determine if the best partial specialization is more specialized than
2187       // the others.
2188       bool Ambiguous = false;
2189       for (SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
2190                                                     PEnd = Matched.end();
2191            P != PEnd; ++P) {
2192         if (P != Best &&
2193             getMoreSpecializedPartialSpecialization(P->Partial, Best->Partial,
2194                                                     PointOfInstantiation)
2195               != Best->Partial) {
2196           Ambiguous = true;
2197           break;
2198         }
2199       }
2200
2201       if (Ambiguous) {
2202         // Partial ordering did not produce a clear winner. Complain.
2203         ClassTemplateSpec->setInvalidDecl();
2204         Diag(PointOfInstantiation, diag::err_partial_spec_ordering_ambiguous)
2205           << ClassTemplateSpec;
2206
2207         // Print the matching partial specializations.
2208         for (SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
2209                                                       PEnd = Matched.end();
2210              P != PEnd; ++P)
2211           Diag(P->Partial->getLocation(), diag::note_partial_spec_match)
2212             << getTemplateArgumentBindingsText(
2213                                             P->Partial->getTemplateParameters(),
2214                                                *P->Args);
2215
2216         return true;
2217       }
2218     }
2219
2220     // Instantiate using the best class template partial specialization.
2221     ClassTemplatePartialSpecializationDecl *OrigPartialSpec = Best->Partial;
2222     while (OrigPartialSpec->getInstantiatedFromMember()) {
2223       // If we've found an explicit specialization of this class template,
2224       // stop here and use that as the pattern.
2225       if (OrigPartialSpec->isMemberSpecialization())
2226         break;
2227
2228       OrigPartialSpec = OrigPartialSpec->getInstantiatedFromMember();
2229     }
2230
2231     Pattern = OrigPartialSpec;
2232     ClassTemplateSpec->setInstantiationOf(Best->Partial, Best->Args);
2233   } else {
2234     //   -- If no matches are found, the instantiation is generated
2235     //      from the primary template.
2236     ClassTemplateDecl *OrigTemplate = Template;
2237     while (OrigTemplate->getInstantiatedFromMemberTemplate()) {
2238       // If we've found an explicit specialization of this class template,
2239       // stop here and use that as the pattern.
2240       if (OrigTemplate->isMemberSpecialization())
2241         break;
2242
2243       OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
2244     }
2245
2246     Pattern = OrigTemplate->getTemplatedDecl();
2247   }
2248
2249   bool Result = InstantiateClass(PointOfInstantiation, ClassTemplateSpec,
2250                                  Pattern,
2251                                 getTemplateInstantiationArgs(ClassTemplateSpec),
2252                                  TSK,
2253                                  Complain);
2254
2255   return Result;
2256 }
2257
2258 /// \brief Instantiates the definitions of all of the member
2259 /// of the given class, which is an instantiation of a class template
2260 /// or a member class of a template.
2261 void
2262 Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
2263                               CXXRecordDecl *Instantiation,
2264                         const MultiLevelTemplateArgumentList &TemplateArgs,
2265                               TemplateSpecializationKind TSK) {
2266   for (DeclContext::decl_iterator D = Instantiation->decls_begin(),
2267                                DEnd = Instantiation->decls_end();
2268        D != DEnd; ++D) {
2269     bool SuppressNew = false;
2270     if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
2271       if (FunctionDecl *Pattern
2272             = Function->getInstantiatedFromMemberFunction()) {
2273         MemberSpecializationInfo *MSInfo
2274           = Function->getMemberSpecializationInfo();
2275         assert(MSInfo && "No member specialization information?");
2276         if (MSInfo->getTemplateSpecializationKind()
2277                                                  == TSK_ExplicitSpecialization)
2278           continue;
2279
2280         if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
2281                                                    Function,
2282                                         MSInfo->getTemplateSpecializationKind(),
2283                                               MSInfo->getPointOfInstantiation(),
2284                                                    SuppressNew) ||
2285             SuppressNew)
2286           continue;
2287
2288         if (Function->isDefined())
2289           continue;
2290
2291         if (TSK == TSK_ExplicitInstantiationDefinition) {
2292           // C++0x [temp.explicit]p8:
2293           //   An explicit instantiation definition that names a class template
2294           //   specialization explicitly instantiates the class template
2295           //   specialization and is only an explicit instantiation definition
2296           //   of members whose definition is visible at the point of
2297           //   instantiation.
2298           if (!Pattern->isDefined())
2299             continue;
2300
2301           Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
2302
2303           InstantiateFunctionDefinition(PointOfInstantiation, Function);
2304         } else {
2305           Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
2306         }
2307       }
2308     } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
2309       if (Var->isStaticDataMember()) {
2310         MemberSpecializationInfo *MSInfo = Var->getMemberSpecializationInfo();
2311         assert(MSInfo && "No member specialization information?");
2312         if (MSInfo->getTemplateSpecializationKind()
2313                                                  == TSK_ExplicitSpecialization)
2314           continue;
2315
2316         if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
2317                                                    Var,
2318                                         MSInfo->getTemplateSpecializationKind(),
2319                                               MSInfo->getPointOfInstantiation(),
2320                                                    SuppressNew) ||
2321             SuppressNew)
2322           continue;
2323
2324         if (TSK == TSK_ExplicitInstantiationDefinition) {
2325           // C++0x [temp.explicit]p8:
2326           //   An explicit instantiation definition that names a class template
2327           //   specialization explicitly instantiates the class template
2328           //   specialization and is only an explicit instantiation definition
2329           //   of members whose definition is visible at the point of
2330           //   instantiation.
2331           if (!Var->getInstantiatedFromStaticDataMember()
2332                                                      ->getOutOfLineDefinition())
2333             continue;
2334
2335           Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
2336           InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
2337         } else {
2338           Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
2339         }
2340       }
2341     } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
2342       // Always skip the injected-class-name, along with any
2343       // redeclarations of nested classes, since both would cause us
2344       // to try to instantiate the members of a class twice.
2345       if (Record->isInjectedClassName() || Record->getPreviousDecl())
2346         continue;
2347
2348       MemberSpecializationInfo *MSInfo = Record->getMemberSpecializationInfo();
2349       assert(MSInfo && "No member specialization information?");
2350
2351       if (MSInfo->getTemplateSpecializationKind()
2352                                                 == TSK_ExplicitSpecialization)
2353         continue;
2354
2355       if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
2356                                                  Record,
2357                                         MSInfo->getTemplateSpecializationKind(),
2358                                               MSInfo->getPointOfInstantiation(),
2359                                                  SuppressNew) ||
2360           SuppressNew)
2361         continue;
2362
2363       CXXRecordDecl *Pattern = Record->getInstantiatedFromMemberClass();
2364       assert(Pattern && "Missing instantiated-from-template information");
2365
2366       if (!Record->getDefinition()) {
2367         if (!Pattern->getDefinition()) {
2368           // C++0x [temp.explicit]p8:
2369           //   An explicit instantiation definition that names a class template
2370           //   specialization explicitly instantiates the class template
2371           //   specialization and is only an explicit instantiation definition
2372           //   of members whose definition is visible at the point of
2373           //   instantiation.
2374           if (TSK == TSK_ExplicitInstantiationDeclaration) {
2375             MSInfo->setTemplateSpecializationKind(TSK);
2376             MSInfo->setPointOfInstantiation(PointOfInstantiation);
2377           }
2378
2379           continue;
2380         }
2381
2382         InstantiateClass(PointOfInstantiation, Record, Pattern,
2383                          TemplateArgs,
2384                          TSK);
2385       } else {
2386         if (TSK == TSK_ExplicitInstantiationDefinition &&
2387             Record->getTemplateSpecializationKind() ==
2388                 TSK_ExplicitInstantiationDeclaration) {
2389           Record->setTemplateSpecializationKind(TSK);
2390           MarkVTableUsed(PointOfInstantiation, Record, true);
2391         }
2392       }
2393
2394       Pattern = cast_or_null<CXXRecordDecl>(Record->getDefinition());
2395       if (Pattern)
2396         InstantiateClassMembers(PointOfInstantiation, Pattern, TemplateArgs,
2397                                 TSK);
2398     } else if (EnumDecl *Enum = dyn_cast<EnumDecl>(*D)) {
2399       MemberSpecializationInfo *MSInfo = Enum->getMemberSpecializationInfo();
2400       assert(MSInfo && "No member specialization information?");
2401
2402       if (MSInfo->getTemplateSpecializationKind()
2403             == TSK_ExplicitSpecialization)
2404         continue;
2405
2406       if (CheckSpecializationInstantiationRedecl(
2407             PointOfInstantiation, TSK, Enum,
2408             MSInfo->getTemplateSpecializationKind(),
2409             MSInfo->getPointOfInstantiation(), SuppressNew) ||
2410           SuppressNew)
2411         continue;
2412
2413       if (Enum->getDefinition())
2414         continue;
2415
2416       EnumDecl *Pattern = Enum->getInstantiatedFromMemberEnum();
2417       assert(Pattern && "Missing instantiated-from-template information");
2418
2419       if (TSK == TSK_ExplicitInstantiationDefinition) {
2420         if (!Pattern->getDefinition())
2421           continue;
2422
2423         InstantiateEnum(PointOfInstantiation, Enum, Pattern, TemplateArgs, TSK);
2424       } else {
2425         MSInfo->setTemplateSpecializationKind(TSK);
2426         MSInfo->setPointOfInstantiation(PointOfInstantiation);
2427       }
2428     }
2429   }
2430 }
2431
2432 /// \brief Instantiate the definitions of all of the members of the
2433 /// given class template specialization, which was named as part of an
2434 /// explicit instantiation.
2435 void
2436 Sema::InstantiateClassTemplateSpecializationMembers(
2437                                            SourceLocation PointOfInstantiation,
2438                             ClassTemplateSpecializationDecl *ClassTemplateSpec,
2439                                                TemplateSpecializationKind TSK) {
2440   // C++0x [temp.explicit]p7:
2441   //   An explicit instantiation that names a class template
2442   //   specialization is an explicit instantion of the same kind
2443   //   (declaration or definition) of each of its members (not
2444   //   including members inherited from base classes) that has not
2445   //   been previously explicitly specialized in the translation unit
2446   //   containing the explicit instantiation, except as described
2447   //   below.
2448   InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
2449                           getTemplateInstantiationArgs(ClassTemplateSpec),
2450                           TSK);
2451 }
2452
2453 StmtResult
2454 Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
2455   if (!S)
2456     return Owned(S);
2457
2458   TemplateInstantiator Instantiator(*this, TemplateArgs,
2459                                     SourceLocation(),
2460                                     DeclarationName());
2461   return Instantiator.TransformStmt(S);
2462 }
2463
2464 ExprResult
2465 Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
2466   if (!E)
2467     return Owned(E);
2468
2469   TemplateInstantiator Instantiator(*this, TemplateArgs,
2470                                     SourceLocation(),
2471                                     DeclarationName());
2472   return Instantiator.TransformExpr(E);
2473 }
2474
2475 bool Sema::SubstExprs(Expr **Exprs, unsigned NumExprs, bool IsCall,
2476                       const MultiLevelTemplateArgumentList &TemplateArgs,
2477                       SmallVectorImpl<Expr *> &Outputs) {
2478   if (NumExprs == 0)
2479     return false;
2480
2481   TemplateInstantiator Instantiator(*this, TemplateArgs,
2482                                     SourceLocation(),
2483                                     DeclarationName());
2484   return Instantiator.TransformExprs(Exprs, NumExprs, IsCall, Outputs);
2485 }
2486
2487 NestedNameSpecifierLoc
2488 Sema::SubstNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS,
2489                         const MultiLevelTemplateArgumentList &TemplateArgs) {
2490   if (!NNS)
2491     return NestedNameSpecifierLoc();
2492
2493   TemplateInstantiator Instantiator(*this, TemplateArgs, NNS.getBeginLoc(),
2494                                     DeclarationName());
2495   return Instantiator.TransformNestedNameSpecifierLoc(NNS);
2496 }
2497
2498 /// \brief Do template substitution on declaration name info.
2499 DeclarationNameInfo
2500 Sema::SubstDeclarationNameInfo(const DeclarationNameInfo &NameInfo,
2501                          const MultiLevelTemplateArgumentList &TemplateArgs) {
2502   TemplateInstantiator Instantiator(*this, TemplateArgs, NameInfo.getLoc(),
2503                                     NameInfo.getName());
2504   return Instantiator.TransformDeclarationNameInfo(NameInfo);
2505 }
2506
2507 TemplateName
2508 Sema::SubstTemplateName(NestedNameSpecifierLoc QualifierLoc,
2509                         TemplateName Name, SourceLocation Loc,
2510                         const MultiLevelTemplateArgumentList &TemplateArgs) {
2511   TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
2512                                     DeclarationName());
2513   CXXScopeSpec SS;
2514   SS.Adopt(QualifierLoc);
2515   return Instantiator.TransformTemplateName(SS, Name, Loc);
2516 }
2517
2518 bool Sema::Subst(const TemplateArgumentLoc *Args, unsigned NumArgs,
2519                  TemplateArgumentListInfo &Result,
2520                  const MultiLevelTemplateArgumentList &TemplateArgs) {
2521   TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
2522                                     DeclarationName());
2523
2524   return Instantiator.TransformTemplateArguments(Args, NumArgs, Result);
2525 }
2526
2527 llvm::PointerUnion<Decl *, LocalInstantiationScope::DeclArgumentPack *> *
2528 LocalInstantiationScope::findInstantiationOf(const Decl *D) {
2529   for (LocalInstantiationScope *Current = this; Current;
2530        Current = Current->Outer) {
2531
2532     // Check if we found something within this scope.
2533     const Decl *CheckD = D;
2534     do {
2535       LocalDeclsMap::iterator Found = Current->LocalDecls.find(CheckD);
2536       if (Found != Current->LocalDecls.end())
2537         return &Found->second;
2538
2539       // If this is a tag declaration, it's possible that we need to look for
2540       // a previous declaration.
2541       if (const TagDecl *Tag = dyn_cast<TagDecl>(CheckD))
2542         CheckD = Tag->getPreviousDecl();
2543       else
2544         CheckD = 0;
2545     } while (CheckD);
2546
2547     // If we aren't combined with our outer scope, we're done.
2548     if (!Current->CombineWithOuterScope)
2549       break;
2550   }
2551
2552   // If we didn't find the decl, then we either have a sema bug, or we have a
2553   // forward reference to a label declaration.  Return null to indicate that
2554   // we have an uninstantiated label.
2555   assert(isa<LabelDecl>(D) && "declaration not instantiated in this scope");
2556   return 0;
2557 }
2558
2559 void LocalInstantiationScope::InstantiatedLocal(const Decl *D, Decl *Inst) {
2560   llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored = LocalDecls[D];
2561   if (Stored.isNull())
2562     Stored = Inst;
2563   else if (Stored.is<Decl *>()) {
2564     assert(Stored.get<Decl *>() == Inst && "Already instantiated this local");
2565     Stored = Inst;
2566   } else
2567     LocalDecls[D].get<DeclArgumentPack *>()->push_back(Inst);
2568 }
2569
2570 void LocalInstantiationScope::InstantiatedLocalPackArg(const Decl *D,
2571                                                        Decl *Inst) {
2572   DeclArgumentPack *Pack = LocalDecls[D].get<DeclArgumentPack *>();
2573   Pack->push_back(Inst);
2574 }
2575
2576 void LocalInstantiationScope::MakeInstantiatedLocalArgPack(const Decl *D) {
2577   llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored = LocalDecls[D];
2578   assert(Stored.isNull() && "Already instantiated this local");
2579   DeclArgumentPack *Pack = new DeclArgumentPack;
2580   Stored = Pack;
2581   ArgumentPacks.push_back(Pack);
2582 }
2583
2584 void LocalInstantiationScope::SetPartiallySubstitutedPack(NamedDecl *Pack,
2585                                           const TemplateArgument *ExplicitArgs,
2586                                                     unsigned NumExplicitArgs) {
2587   assert((!PartiallySubstitutedPack || PartiallySubstitutedPack == Pack) &&
2588          "Already have a partially-substituted pack");
2589   assert((!PartiallySubstitutedPack
2590           || NumArgsInPartiallySubstitutedPack == NumExplicitArgs) &&
2591          "Wrong number of arguments in partially-substituted pack");
2592   PartiallySubstitutedPack = Pack;
2593   ArgsInPartiallySubstitutedPack = ExplicitArgs;
2594   NumArgsInPartiallySubstitutedPack = NumExplicitArgs;
2595 }
2596
2597 NamedDecl *LocalInstantiationScope::getPartiallySubstitutedPack(
2598                                          const TemplateArgument **ExplicitArgs,
2599                                               unsigned *NumExplicitArgs) const {
2600   if (ExplicitArgs)
2601     *ExplicitArgs = 0;
2602   if (NumExplicitArgs)
2603     *NumExplicitArgs = 0;
2604
2605   for (const LocalInstantiationScope *Current = this; Current;
2606        Current = Current->Outer) {
2607     if (Current->PartiallySubstitutedPack) {
2608       if (ExplicitArgs)
2609         *ExplicitArgs = Current->ArgsInPartiallySubstitutedPack;
2610       if (NumExplicitArgs)
2611         *NumExplicitArgs = Current->NumArgsInPartiallySubstitutedPack;
2612
2613       return Current->PartiallySubstitutedPack;
2614     }
2615
2616     if (!Current->CombineWithOuterScope)
2617       break;
2618   }
2619
2620   return 0;
2621 }