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