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