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