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