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