SemaTemplateInstantiate.cpp revision 5195bbb1a924cd1942da624fa30765e695f1225b 
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 "Sema.h"
14#include "TreeTransform.h"
15#include "Lookup.h"
16#include "clang/AST/ASTConsumer.h"
17#include "clang/AST/ASTContext.h"
18#include "clang/AST/Expr.h"
19#include "clang/AST/DeclTemplate.h"
20#include "clang/Parse/DeclSpec.h"
21#include "clang/Basic/LangOptions.h"
22
23using namespace clang;
24
25//===----------------------------------------------------------------------===/
26// Template Instantiation Support
27//===----------------------------------------------------------------------===/
28
29/// \brief Retrieve the template argument list(s) that should be used to
30/// instantiate the definition of the given declaration.
31///
32/// \param D the declaration for which we are computing template instantiation
33/// arguments.
34///
35/// \param Innermost if non-NULL, the innermost template argument list.
36///
37/// \param RelativeToPrimary true if we should get the template
38/// arguments relative to the primary template, even when we're
39/// dealing with a specialization. This is only relevant for function
40/// template specializations.
41///
42/// \param Pattern If non-NULL, indicates the pattern from which we will be
43/// instantiating the definition of the given declaration, \p D. This is
44/// used to determine the proper set of template instantiation arguments for
45/// friend function template specializations.
46MultiLevelTemplateArgumentList
47Sema::getTemplateInstantiationArgs(NamedDecl *D,
48                                   const TemplateArgumentList *Innermost,
49                                   bool RelativeToPrimary,
50                                   const FunctionDecl *Pattern) {
51  // Accumulate the set of template argument lists in this structure.
52  MultiLevelTemplateArgumentList Result;
53
54  if (Innermost)
55    Result.addOuterTemplateArguments(Innermost);
56
57  DeclContext *Ctx = dyn_cast<DeclContext>(D);
58  if (!Ctx)
59    Ctx = D->getDeclContext();
60
61  while (!Ctx->isFileContext()) {
62    // Add template arguments from a class template instantiation.
63    if (ClassTemplateSpecializationDecl *Spec
64          = dyn_cast<ClassTemplateSpecializationDecl>(Ctx)) {
65      // We're done when we hit an explicit specialization.
66      if (Spec->getSpecializationKind() == TSK_ExplicitSpecialization)
67        break;
68
69      Result.addOuterTemplateArguments(&Spec->getTemplateInstantiationArgs());
70
71      // If this class template specialization was instantiated from a
72      // specialized member that is a class template, we're done.
73      assert(Spec->getSpecializedTemplate() && "No class template?");
74      if (Spec->getSpecializedTemplate()->isMemberSpecialization())
75        break;
76    }
77    // Add template arguments from a function template specialization.
78    else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Ctx)) {
79      if (!RelativeToPrimary &&
80          Function->getTemplateSpecializationKind()
81                                                  == TSK_ExplicitSpecialization)
82        break;
83
84      if (const TemplateArgumentList *TemplateArgs
85            = Function->getTemplateSpecializationArgs()) {
86        // Add the template arguments for this specialization.
87        Result.addOuterTemplateArguments(TemplateArgs);
88
89        // If this function was instantiated from a specialized member that is
90        // a function template, we're done.
91        assert(Function->getPrimaryTemplate() && "No function template?");
92        if (Function->getPrimaryTemplate()->isMemberSpecialization())
93          break;
94      }
95
96      // If this is a friend declaration and it declares an entity at
97      // namespace scope, take arguments from its lexical parent
98      // instead of its semantic parent, unless of course the pattern we're
99      // instantiating actually comes from the file's context!
100      if (Function->getFriendObjectKind() &&
101          Function->getDeclContext()->isFileContext() &&
102          (!Pattern || !Pattern->getLexicalDeclContext()->isFileContext())) {
103        Ctx = Function->getLexicalDeclContext();
104        RelativeToPrimary = false;
105        continue;
106      }
107    }
108
109    Ctx = Ctx->getParent();
110    RelativeToPrimary = false;
111  }
112
113  return Result;
114}
115
116bool Sema::ActiveTemplateInstantiation::isInstantiationRecord() const {
117  switch (Kind) {
118  case TemplateInstantiation:
119  case DefaultTemplateArgumentInstantiation:
120  case DefaultFunctionArgumentInstantiation:
121    return true;
122
123  case ExplicitTemplateArgumentSubstitution:
124  case DeducedTemplateArgumentSubstitution:
125  case PriorTemplateArgumentSubstitution:
126  case DefaultTemplateArgumentChecking:
127    return false;
128  }
129
130  return true;
131}
132
133Sema::InstantiatingTemplate::
134InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
135                      Decl *Entity,
136                      SourceRange InstantiationRange)
137  :  SemaRef(SemaRef) {
138
139  Invalid = CheckInstantiationDepth(PointOfInstantiation,
140                                    InstantiationRange);
141  if (!Invalid) {
142    ActiveTemplateInstantiation Inst;
143    Inst.Kind = ActiveTemplateInstantiation::TemplateInstantiation;
144    Inst.PointOfInstantiation = PointOfInstantiation;
145    Inst.Entity = reinterpret_cast<uintptr_t>(Entity);
146    Inst.TemplateArgs = 0;
147    Inst.NumTemplateArgs = 0;
148    Inst.InstantiationRange = InstantiationRange;
149    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
150  }
151}
152
153Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
154                                         SourceLocation PointOfInstantiation,
155                                         TemplateDecl *Template,
156                                         const TemplateArgument *TemplateArgs,
157                                         unsigned NumTemplateArgs,
158                                         SourceRange InstantiationRange)
159  : SemaRef(SemaRef) {
160
161  Invalid = CheckInstantiationDepth(PointOfInstantiation,
162                                    InstantiationRange);
163  if (!Invalid) {
164    ActiveTemplateInstantiation Inst;
165    Inst.Kind
166      = ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation;
167    Inst.PointOfInstantiation = PointOfInstantiation;
168    Inst.Entity = reinterpret_cast<uintptr_t>(Template);
169    Inst.TemplateArgs = TemplateArgs;
170    Inst.NumTemplateArgs = NumTemplateArgs;
171    Inst.InstantiationRange = InstantiationRange;
172    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
173  }
174}
175
176Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
177                                         SourceLocation PointOfInstantiation,
178                                      FunctionTemplateDecl *FunctionTemplate,
179                                        const TemplateArgument *TemplateArgs,
180                                                   unsigned NumTemplateArgs,
181                         ActiveTemplateInstantiation::InstantiationKind Kind,
182                                              SourceRange InstantiationRange)
183: SemaRef(SemaRef) {
184
185  Invalid = CheckInstantiationDepth(PointOfInstantiation,
186                                    InstantiationRange);
187  if (!Invalid) {
188    ActiveTemplateInstantiation Inst;
189    Inst.Kind = Kind;
190    Inst.PointOfInstantiation = PointOfInstantiation;
191    Inst.Entity = reinterpret_cast<uintptr_t>(FunctionTemplate);
192    Inst.TemplateArgs = TemplateArgs;
193    Inst.NumTemplateArgs = NumTemplateArgs;
194    Inst.InstantiationRange = InstantiationRange;
195    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
196
197    if (!Inst.isInstantiationRecord())
198      ++SemaRef.NonInstantiationEntries;
199  }
200}
201
202Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
203                                         SourceLocation PointOfInstantiation,
204                          ClassTemplatePartialSpecializationDecl *PartialSpec,
205                                         const TemplateArgument *TemplateArgs,
206                                         unsigned NumTemplateArgs,
207                                         SourceRange InstantiationRange)
208  : SemaRef(SemaRef) {
209
210  Invalid = false;
211
212  ActiveTemplateInstantiation Inst;
213  Inst.Kind = ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution;
214  Inst.PointOfInstantiation = PointOfInstantiation;
215  Inst.Entity = reinterpret_cast<uintptr_t>(PartialSpec);
216  Inst.TemplateArgs = TemplateArgs;
217  Inst.NumTemplateArgs = NumTemplateArgs;
218  Inst.InstantiationRange = InstantiationRange;
219  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
220
221  assert(!Inst.isInstantiationRecord());
222  ++SemaRef.NonInstantiationEntries;
223}
224
225Sema::InstantiatingTemplate::InstantiatingTemplate(Sema &SemaRef,
226                                          SourceLocation PointOfInstantiation,
227                                          ParmVarDecl *Param,
228                                          const TemplateArgument *TemplateArgs,
229                                          unsigned NumTemplateArgs,
230                                          SourceRange InstantiationRange)
231  : SemaRef(SemaRef) {
232
233  Invalid = CheckInstantiationDepth(PointOfInstantiation, InstantiationRange);
234
235  if (!Invalid) {
236    ActiveTemplateInstantiation Inst;
237    Inst.Kind
238      = ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation;
239    Inst.PointOfInstantiation = PointOfInstantiation;
240    Inst.Entity = reinterpret_cast<uintptr_t>(Param);
241    Inst.TemplateArgs = TemplateArgs;
242    Inst.NumTemplateArgs = NumTemplateArgs;
243    Inst.InstantiationRange = InstantiationRange;
244    SemaRef.ActiveTemplateInstantiations.push_back(Inst);
245  }
246}
247
248Sema::InstantiatingTemplate::
249InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
250                      TemplateDecl *Template,
251                      NonTypeTemplateParmDecl *Param,
252                      const TemplateArgument *TemplateArgs,
253                      unsigned NumTemplateArgs,
254                      SourceRange InstantiationRange) : SemaRef(SemaRef) {
255  Invalid = false;
256
257  ActiveTemplateInstantiation Inst;
258  Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
259  Inst.PointOfInstantiation = PointOfInstantiation;
260  Inst.Template = Template;
261  Inst.Entity = reinterpret_cast<uintptr_t>(Param);
262  Inst.TemplateArgs = TemplateArgs;
263  Inst.NumTemplateArgs = NumTemplateArgs;
264  Inst.InstantiationRange = InstantiationRange;
265  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
266
267  assert(!Inst.isInstantiationRecord());
268  ++SemaRef.NonInstantiationEntries;
269}
270
271Sema::InstantiatingTemplate::
272InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
273                      TemplateDecl *Template,
274                      TemplateTemplateParmDecl *Param,
275                      const TemplateArgument *TemplateArgs,
276                      unsigned NumTemplateArgs,
277                      SourceRange InstantiationRange) : SemaRef(SemaRef) {
278  Invalid = false;
279  ActiveTemplateInstantiation Inst;
280  Inst.Kind = ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution;
281  Inst.PointOfInstantiation = PointOfInstantiation;
282  Inst.Template = Template;
283  Inst.Entity = reinterpret_cast<uintptr_t>(Param);
284  Inst.TemplateArgs = TemplateArgs;
285  Inst.NumTemplateArgs = NumTemplateArgs;
286  Inst.InstantiationRange = InstantiationRange;
287  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
288
289  assert(!Inst.isInstantiationRecord());
290  ++SemaRef.NonInstantiationEntries;
291}
292
293Sema::InstantiatingTemplate::
294InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation,
295                      TemplateDecl *Template,
296                      NamedDecl *Param,
297                      const TemplateArgument *TemplateArgs,
298                      unsigned NumTemplateArgs,
299                      SourceRange InstantiationRange) : SemaRef(SemaRef) {
300  Invalid = false;
301
302  ActiveTemplateInstantiation Inst;
303  Inst.Kind = ActiveTemplateInstantiation::DefaultTemplateArgumentChecking;
304  Inst.PointOfInstantiation = PointOfInstantiation;
305  Inst.Template = Template;
306  Inst.Entity = reinterpret_cast<uintptr_t>(Param);
307  Inst.TemplateArgs = TemplateArgs;
308  Inst.NumTemplateArgs = NumTemplateArgs;
309  Inst.InstantiationRange = InstantiationRange;
310  SemaRef.ActiveTemplateInstantiations.push_back(Inst);
311
312  assert(!Inst.isInstantiationRecord());
313  ++SemaRef.NonInstantiationEntries;
314}
315
316void Sema::InstantiatingTemplate::Clear() {
317  if (!Invalid) {
318    if (!SemaRef.ActiveTemplateInstantiations.back().isInstantiationRecord()) {
319      assert(SemaRef.NonInstantiationEntries > 0);
320      --SemaRef.NonInstantiationEntries;
321    }
322
323    SemaRef.ActiveTemplateInstantiations.pop_back();
324    Invalid = true;
325  }
326}
327
328bool Sema::InstantiatingTemplate::CheckInstantiationDepth(
329                                        SourceLocation PointOfInstantiation,
330                                           SourceRange InstantiationRange) {
331  assert(SemaRef.NonInstantiationEntries <=
332                                   SemaRef.ActiveTemplateInstantiations.size());
333  if ((SemaRef.ActiveTemplateInstantiations.size() -
334          SemaRef.NonInstantiationEntries)
335        <= SemaRef.getLangOptions().InstantiationDepth)
336    return false;
337
338  SemaRef.Diag(PointOfInstantiation,
339               diag::err_template_recursion_depth_exceeded)
340    << SemaRef.getLangOptions().InstantiationDepth
341    << InstantiationRange;
342  SemaRef.Diag(PointOfInstantiation, diag::note_template_recursion_depth)
343    << SemaRef.getLangOptions().InstantiationDepth;
344  return true;
345}
346
347/// \brief Prints the current instantiation stack through a series of
348/// notes.
349void Sema::PrintInstantiationStack() {
350  // Determine which template instantiations to skip, if any.
351  unsigned SkipStart = ActiveTemplateInstantiations.size(), SkipEnd = SkipStart;
352  unsigned Limit = Diags.getTemplateBacktraceLimit();
353  if (Limit && Limit < ActiveTemplateInstantiations.size()) {
354    SkipStart = Limit / 2 + Limit % 2;
355    SkipEnd = ActiveTemplateInstantiations.size() - Limit / 2;
356  }
357
358  // FIXME: In all of these cases, we need to show the template arguments
359  unsigned InstantiationIdx = 0;
360  for (llvm::SmallVector<ActiveTemplateInstantiation, 16>::reverse_iterator
361         Active = ActiveTemplateInstantiations.rbegin(),
362         ActiveEnd = ActiveTemplateInstantiations.rend();
363       Active != ActiveEnd;
364       ++Active, ++InstantiationIdx) {
365    // Skip this instantiation?
366    if (InstantiationIdx >= SkipStart && InstantiationIdx < SkipEnd) {
367      if (InstantiationIdx == SkipStart) {
368        // Note that we're skipping instantiations.
369        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
370                     diag::note_instantiation_contexts_suppressed)
371          << unsigned(ActiveTemplateInstantiations.size() - Limit);
372      }
373      continue;
374    }
375
376    switch (Active->Kind) {
377    case ActiveTemplateInstantiation::TemplateInstantiation: {
378      Decl *D = reinterpret_cast<Decl *>(Active->Entity);
379      if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D)) {
380        unsigned DiagID = diag::note_template_member_class_here;
381        if (isa<ClassTemplateSpecializationDecl>(Record))
382          DiagID = diag::note_template_class_instantiation_here;
383        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
384                     DiagID)
385          << Context.getTypeDeclType(Record)
386          << Active->InstantiationRange;
387      } else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D)) {
388        unsigned DiagID;
389        if (Function->getPrimaryTemplate())
390          DiagID = diag::note_function_template_spec_here;
391        else
392          DiagID = diag::note_template_member_function_here;
393        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
394                     DiagID)
395          << Function
396          << Active->InstantiationRange;
397      } else {
398        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
399                     diag::note_template_static_data_member_def_here)
400          << cast<VarDecl>(D)
401          << Active->InstantiationRange;
402      }
403      break;
404    }
405
406    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation: {
407      TemplateDecl *Template = cast<TemplateDecl>((Decl *)Active->Entity);
408      std::string TemplateArgsStr
409        = TemplateSpecializationType::PrintTemplateArgumentList(
410                                                         Active->TemplateArgs,
411                                                      Active->NumTemplateArgs,
412                                                      Context.PrintingPolicy);
413      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
414                   diag::note_default_arg_instantiation_here)
415        << (Template->getNameAsString() + TemplateArgsStr)
416        << Active->InstantiationRange;
417      break;
418    }
419
420    case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution: {
421      FunctionTemplateDecl *FnTmpl
422        = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
423      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
424                   diag::note_explicit_template_arg_substitution_here)
425        << FnTmpl
426        << getTemplateArgumentBindingsText(FnTmpl->getTemplateParameters(),
427                                           Active->TemplateArgs,
428                                           Active->NumTemplateArgs)
429        << Active->InstantiationRange;
430      break;
431    }
432
433    case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
434      if (ClassTemplatePartialSpecializationDecl *PartialSpec
435            = dyn_cast<ClassTemplatePartialSpecializationDecl>(
436                                                    (Decl *)Active->Entity)) {
437        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
438                     diag::note_partial_spec_deduct_instantiation_here)
439          << Context.getTypeDeclType(PartialSpec)
440          << getTemplateArgumentBindingsText(
441                                         PartialSpec->getTemplateParameters(),
442                                             Active->TemplateArgs,
443                                             Active->NumTemplateArgs)
444          << Active->InstantiationRange;
445      } else {
446        FunctionTemplateDecl *FnTmpl
447          = cast<FunctionTemplateDecl>((Decl *)Active->Entity);
448        Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
449                     diag::note_function_template_deduction_instantiation_here)
450          << FnTmpl
451          << getTemplateArgumentBindingsText(FnTmpl->getTemplateParameters(),
452                                             Active->TemplateArgs,
453                                             Active->NumTemplateArgs)
454          << Active->InstantiationRange;
455      }
456      break;
457
458    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation: {
459      ParmVarDecl *Param = cast<ParmVarDecl>((Decl *)Active->Entity);
460      FunctionDecl *FD = cast<FunctionDecl>(Param->getDeclContext());
461
462      std::string TemplateArgsStr
463        = TemplateSpecializationType::PrintTemplateArgumentList(
464                                                         Active->TemplateArgs,
465                                                      Active->NumTemplateArgs,
466                                                      Context.PrintingPolicy);
467      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
468                   diag::note_default_function_arg_instantiation_here)
469        << (FD->getNameAsString() + TemplateArgsStr)
470        << Active->InstantiationRange;
471      break;
472    }
473
474    case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution: {
475      NamedDecl *Parm = cast<NamedDecl>((Decl *)Active->Entity);
476      std::string Name;
477      if (!Parm->getName().empty())
478        Name = std::string(" '") + Parm->getName().str() + "'";
479
480      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
481                   diag::note_prior_template_arg_substitution)
482        << isa<TemplateTemplateParmDecl>(Parm)
483        << Name
484        << getTemplateArgumentBindingsText(
485                                    Active->Template->getTemplateParameters(),
486                                           Active->TemplateArgs,
487                                           Active->NumTemplateArgs)
488        << Active->InstantiationRange;
489      break;
490    }
491
492    case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking: {
493      Diags.Report(FullSourceLoc(Active->PointOfInstantiation, SourceMgr),
494                   diag::note_template_default_arg_checking)
495        << getTemplateArgumentBindingsText(
496                                     Active->Template->getTemplateParameters(),
497                                           Active->TemplateArgs,
498                                           Active->NumTemplateArgs)
499        << Active->InstantiationRange;
500      break;
501    }
502    }
503  }
504}
505
506bool Sema::isSFINAEContext() const {
507  using llvm::SmallVector;
508  for (SmallVector<ActiveTemplateInstantiation, 16>::const_reverse_iterator
509         Active = ActiveTemplateInstantiations.rbegin(),
510         ActiveEnd = ActiveTemplateInstantiations.rend();
511       Active != ActiveEnd;
512       ++Active)
513  {
514    switch(Active->Kind) {
515    case ActiveTemplateInstantiation::TemplateInstantiation:
516    case ActiveTemplateInstantiation::DefaultFunctionArgumentInstantiation:
517      // This is a template instantiation, so there is no SFINAE.
518      return false;
519
520    case ActiveTemplateInstantiation::DefaultTemplateArgumentInstantiation:
521    case ActiveTemplateInstantiation::PriorTemplateArgumentSubstitution:
522    case ActiveTemplateInstantiation::DefaultTemplateArgumentChecking:
523      // A default template argument instantiation and substitution into
524      // template parameters with arguments for prior parameters may or may
525      // not be a SFINAE context; look further up the stack.
526      break;
527
528    case ActiveTemplateInstantiation::ExplicitTemplateArgumentSubstitution:
529    case ActiveTemplateInstantiation::DeducedTemplateArgumentSubstitution:
530      // We're either substitution explicitly-specified template arguments
531      // or deduced template arguments, so SFINAE applies.
532      return true;
533    }
534  }
535
536  return false;
537}
538
539//===----------------------------------------------------------------------===/
540// Template Instantiation for Types
541//===----------------------------------------------------------------------===/
542namespace {
543  class TemplateInstantiator : public TreeTransform<TemplateInstantiator> {
544    const MultiLevelTemplateArgumentList &TemplateArgs;
545    SourceLocation Loc;
546    DeclarationName Entity;
547
548  public:
549    typedef TreeTransform<TemplateInstantiator> inherited;
550
551    TemplateInstantiator(Sema &SemaRef,
552                         const MultiLevelTemplateArgumentList &TemplateArgs,
553                         SourceLocation Loc,
554                         DeclarationName Entity)
555      : inherited(SemaRef), TemplateArgs(TemplateArgs), Loc(Loc),
556        Entity(Entity) { }
557
558    /// \brief Determine whether the given type \p T has already been
559    /// transformed.
560    ///
561    /// For the purposes of template instantiation, a type has already been
562    /// transformed if it is NULL or if it is not dependent.
563    bool AlreadyTransformed(QualType T);
564
565    /// \brief Returns the location of the entity being instantiated, if known.
566    SourceLocation getBaseLocation() { return Loc; }
567
568    /// \brief Returns the name of the entity being instantiated, if any.
569    DeclarationName getBaseEntity() { return Entity; }
570
571    /// \brief Sets the "base" location and entity when that
572    /// information is known based on another transformation.
573    void setBase(SourceLocation Loc, DeclarationName Entity) {
574      this->Loc = Loc;
575      this->Entity = Entity;
576    }
577
578    /// \brief Transform the given declaration by instantiating a reference to
579    /// this declaration.
580    Decl *TransformDecl(SourceLocation Loc, Decl *D);
581
582    /// \brief Transform the definition of the given declaration by
583    /// instantiating it.
584    Decl *TransformDefinition(SourceLocation Loc, Decl *D);
585
586    /// \bried Transform the first qualifier within a scope by instantiating the
587    /// declaration.
588    NamedDecl *TransformFirstQualifierInScope(NamedDecl *D, SourceLocation Loc);
589
590    /// \brief Rebuild the exception declaration and register the declaration
591    /// as an instantiated local.
592    VarDecl *RebuildExceptionDecl(VarDecl *ExceptionDecl, QualType T,
593                                  TypeSourceInfo *Declarator,
594                                  IdentifierInfo *Name,
595                                  SourceLocation Loc, SourceRange TypeRange);
596
597    /// \brief Rebuild the Objective-C exception declaration and register the
598    /// declaration as an instantiated local.
599    VarDecl *RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
600                                      TypeSourceInfo *TSInfo, QualType T);
601
602    /// \brief Check for tag mismatches when instantiating an
603    /// elaborated type.
604    QualType RebuildElaboratedType(ElaboratedTypeKeyword Keyword,
605                                   NestedNameSpecifier *NNS, QualType T);
606
607    Sema::OwningExprResult TransformPredefinedExpr(PredefinedExpr *E);
608    Sema::OwningExprResult TransformDeclRefExpr(DeclRefExpr *E);
609    Sema::OwningExprResult TransformCXXDefaultArgExpr(CXXDefaultArgExpr *E);
610    Sema::OwningExprResult TransformTemplateParmRefExpr(DeclRefExpr *E,
611                                                NonTypeTemplateParmDecl *D);
612
613    QualType TransformFunctionProtoType(TypeLocBuilder &TLB,
614                                        FunctionProtoTypeLoc TL,
615                                        QualType ObjectType);
616    ParmVarDecl *TransformFunctionTypeParam(ParmVarDecl *OldParm);
617
618    /// \brief Transforms a template type parameter type by performing
619    /// substitution of the corresponding template type argument.
620    QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
621                                           TemplateTypeParmTypeLoc TL,
622                                           QualType ObjectType);
623
624    Sema::OwningExprResult TransformCallExpr(CallExpr *CE) {
625      getSema().CallsUndergoingInstantiation.push_back(CE);
626      OwningExprResult Result =
627          TreeTransform<TemplateInstantiator>::TransformCallExpr(CE);
628      getSema().CallsUndergoingInstantiation.pop_back();
629      return move(Result);
630    }
631  };
632}
633
634bool TemplateInstantiator::AlreadyTransformed(QualType T) {
635  if (T.isNull())
636    return true;
637
638  if (T->isDependentType() || T->isVariablyModifiedType())
639    return false;
640
641  getSema().MarkDeclarationsReferencedInType(Loc, T);
642  return true;
643}
644
645Decl *TemplateInstantiator::TransformDecl(SourceLocation Loc, Decl *D) {
646  if (!D)
647    return 0;
648
649  if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
650    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
651      // If the corresponding template argument is NULL or non-existent, it's
652      // because we are performing instantiation from explicitly-specified
653      // template arguments in a function template, but there were some
654      // arguments left unspecified.
655      if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
656                                            TTP->getPosition()))
657        return D;
658
659      TemplateName Template
660        = TemplateArgs(TTP->getDepth(), TTP->getPosition()).getAsTemplate();
661      assert(!Template.isNull() && Template.getAsTemplateDecl() &&
662             "Wrong kind of template template argument");
663      return Template.getAsTemplateDecl();
664    }
665
666    // Fall through to find the instantiated declaration for this template
667    // template parameter.
668  }
669
670  return SemaRef.FindInstantiatedDecl(Loc, cast<NamedDecl>(D), TemplateArgs);
671}
672
673Decl *TemplateInstantiator::TransformDefinition(SourceLocation Loc, Decl *D) {
674  Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
675  if (!Inst)
676    return 0;
677
678  getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
679  return Inst;
680}
681
682NamedDecl *
683TemplateInstantiator::TransformFirstQualifierInScope(NamedDecl *D,
684                                                     SourceLocation Loc) {
685  // If the first part of the nested-name-specifier was a template type
686  // parameter, instantiate that type parameter down to a tag type.
687  if (TemplateTypeParmDecl *TTPD = dyn_cast_or_null<TemplateTypeParmDecl>(D)) {
688    const TemplateTypeParmType *TTP
689      = cast<TemplateTypeParmType>(getSema().Context.getTypeDeclType(TTPD));
690    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
691      QualType T = TemplateArgs(TTP->getDepth(), TTP->getIndex()).getAsType();
692      if (T.isNull())
693        return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
694
695      if (const TagType *Tag = T->getAs<TagType>())
696        return Tag->getDecl();
697
698      // The resulting type is not a tag; complain.
699      getSema().Diag(Loc, diag::err_nested_name_spec_non_tag) << T;
700      return 0;
701    }
702  }
703
704  return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
705}
706
707VarDecl *
708TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
709                                           QualType T,
710                                           TypeSourceInfo *Declarator,
711                                           IdentifierInfo *Name,
712                                           SourceLocation Loc,
713                                           SourceRange TypeRange) {
714  VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, T, Declarator,
715                                                 Name, Loc, TypeRange);
716  if (Var)
717    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
718  return Var;
719}
720
721VarDecl *TemplateInstantiator::RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
722                                                        TypeSourceInfo *TSInfo,
723                                                        QualType T) {
724  VarDecl *Var = inherited::RebuildObjCExceptionDecl(ExceptionDecl, TSInfo, T);
725  if (Var)
726    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
727  return Var;
728}
729
730QualType
731TemplateInstantiator::RebuildElaboratedType(ElaboratedTypeKeyword Keyword,
732                                            NestedNameSpecifier *NNS,
733                                            QualType T) {
734  if (const TagType *TT = T->getAs<TagType>()) {
735    TagDecl* TD = TT->getDecl();
736
737    // FIXME: this location is very wrong;  we really need typelocs.
738    SourceLocation TagLocation = TD->getTagKeywordLoc();
739
740    // FIXME: type might be anonymous.
741    IdentifierInfo *Id = TD->getIdentifier();
742
743    // TODO: should we even warn on struct/class mismatches for this?  Seems
744    // like it's likely to produce a lot of spurious errors.
745    if (Keyword != ETK_None && Keyword != ETK_Typename) {
746      TagTypeKind Kind = TypeWithKeyword::getTagTypeKindForKeyword(Keyword);
747      if (!SemaRef.isAcceptableTagRedeclaration(TD, Kind, TagLocation, *Id)) {
748        SemaRef.Diag(TagLocation, diag::err_use_with_wrong_tag)
749          << Id
750          << FixItHint::CreateReplacement(SourceRange(TagLocation),
751                                          TD->getKindName());
752        SemaRef.Diag(TD->getLocation(), diag::note_previous_use);
753      }
754    }
755  }
756
757  return TreeTransform<TemplateInstantiator>::RebuildElaboratedType(Keyword,
758                                                                    NNS, T);
759}
760
761Sema::OwningExprResult
762TemplateInstantiator::TransformPredefinedExpr(PredefinedExpr *E) {
763  if (!E->isTypeDependent())
764    return SemaRef.Owned(E->Retain());
765
766  FunctionDecl *currentDecl = getSema().getCurFunctionDecl();
767  assert(currentDecl && "Must have current function declaration when "
768                        "instantiating.");
769
770  PredefinedExpr::IdentType IT = E->getIdentType();
771
772  unsigned Length = PredefinedExpr::ComputeName(IT, currentDecl).length();
773
774  llvm::APInt LengthI(32, Length + 1);
775  QualType ResTy = getSema().Context.CharTy.withConst();
776  ResTy = getSema().Context.getConstantArrayType(ResTy, LengthI,
777                                                 ArrayType::Normal, 0);
778  PredefinedExpr *PE =
779    new (getSema().Context) PredefinedExpr(E->getLocation(), ResTy, IT);
780  return getSema().Owned(PE);
781}
782
783Sema::OwningExprResult
784TemplateInstantiator::TransformTemplateParmRefExpr(DeclRefExpr *E,
785                                               NonTypeTemplateParmDecl *NTTP) {
786  // If the corresponding template argument is NULL or non-existent, it's
787  // because we are performing instantiation from explicitly-specified
788  // template arguments in a function template, but there were some
789  // arguments left unspecified.
790  if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
791                                        NTTP->getPosition()))
792    return SemaRef.Owned(E->Retain());
793
794  const TemplateArgument &Arg = TemplateArgs(NTTP->getDepth(),
795                                             NTTP->getPosition());
796
797  // The template argument itself might be an expression, in which
798  // case we just return that expression.
799  if (Arg.getKind() == TemplateArgument::Expression)
800    return SemaRef.Owned(Arg.getAsExpr()->Retain());
801
802  if (Arg.getKind() == TemplateArgument::Declaration) {
803    ValueDecl *VD = cast<ValueDecl>(Arg.getAsDecl());
804
805    // Find the instantiation of the template argument.  This is
806    // required for nested templates.
807    VD = cast_or_null<ValueDecl>(
808                            getSema().FindInstantiatedDecl(E->getLocation(),
809                                                           VD, TemplateArgs));
810    if (!VD)
811      return SemaRef.ExprError();
812
813    // Derive the type we want the substituted decl to have.  This had
814    // better be non-dependent, or these checks will have serious problems.
815    QualType TargetType = SemaRef.SubstType(NTTP->getType(), TemplateArgs,
816                                            E->getLocation(),
817                                            DeclarationName());
818    assert(!TargetType.isNull() && "type substitution failed for param type");
819    assert(!TargetType->isDependentType() && "param type still dependent");
820    return SemaRef.BuildExpressionFromDeclTemplateArgument(Arg,
821                                                           TargetType,
822                                                           E->getLocation());
823  }
824
825  return SemaRef.BuildExpressionFromIntegralTemplateArgument(Arg,
826                                                E->getSourceRange().getBegin());
827}
828
829
830Sema::OwningExprResult
831TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E) {
832  NamedDecl *D = E->getDecl();
833  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
834    if (NTTP->getDepth() < TemplateArgs.getNumLevels())
835      return TransformTemplateParmRefExpr(E, NTTP);
836
837    // We have a non-type template parameter that isn't fully substituted;
838    // FindInstantiatedDecl will find it in the local instantiation scope.
839  }
840
841  return TreeTransform<TemplateInstantiator>::TransformDeclRefExpr(E);
842}
843
844Sema::OwningExprResult TemplateInstantiator::TransformCXXDefaultArgExpr(
845    CXXDefaultArgExpr *E) {
846  assert(!cast<FunctionDecl>(E->getParam()->getDeclContext())->
847             getDescribedFunctionTemplate() &&
848         "Default arg expressions are never formed in dependent cases.");
849  return SemaRef.BuildCXXDefaultArgExpr(E->getUsedLocation(),
850                           cast<FunctionDecl>(E->getParam()->getDeclContext()),
851                                        E->getParam());
852}
853
854QualType TemplateInstantiator::TransformFunctionProtoType(TypeLocBuilder &TLB,
855                                                        FunctionProtoTypeLoc TL,
856                                                          QualType ObjectType) {
857  // We need a local instantiation scope for this function prototype.
858  Sema::LocalInstantiationScope Scope(SemaRef, /*CombineWithOuterScope=*/true);
859  return inherited::TransformFunctionProtoType(TLB, TL, ObjectType);
860}
861
862ParmVarDecl *
863TemplateInstantiator::TransformFunctionTypeParam(ParmVarDecl *OldParm) {
864  return SemaRef.SubstParmVarDecl(OldParm, TemplateArgs);
865}
866
867QualType
868TemplateInstantiator::TransformTemplateTypeParmType(TypeLocBuilder &TLB,
869                                                TemplateTypeParmTypeLoc TL,
870                                                    QualType ObjectType) {
871  TemplateTypeParmType *T = TL.getTypePtr();
872  if (T->getDepth() < TemplateArgs.getNumLevels()) {
873    // Replace the template type parameter with its corresponding
874    // template argument.
875
876    // If the corresponding template argument is NULL or doesn't exist, it's
877    // because we are performing instantiation from explicitly-specified
878    // template arguments in a function template class, but there were some
879    // arguments left unspecified.
880    if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex())) {
881      TemplateTypeParmTypeLoc NewTL
882        = TLB.push<TemplateTypeParmTypeLoc>(TL.getType());
883      NewTL.setNameLoc(TL.getNameLoc());
884      return TL.getType();
885    }
886
887    assert(TemplateArgs(T->getDepth(), T->getIndex()).getKind()
888             == TemplateArgument::Type &&
889           "Template argument kind mismatch");
890
891    QualType Replacement
892      = TemplateArgs(T->getDepth(), T->getIndex()).getAsType();
893
894    // TODO: only do this uniquing once, at the start of instantiation.
895    QualType Result
896      = getSema().Context.getSubstTemplateTypeParmType(T, Replacement);
897    SubstTemplateTypeParmTypeLoc NewTL
898      = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
899    NewTL.setNameLoc(TL.getNameLoc());
900    return Result;
901  }
902
903  // The template type parameter comes from an inner template (e.g.,
904  // the template parameter list of a member template inside the
905  // template we are instantiating). Create a new template type
906  // parameter with the template "level" reduced by one.
907  QualType Result
908    = getSema().Context.getTemplateTypeParmType(T->getDepth()
909                                                 - TemplateArgs.getNumLevels(),
910                                                T->getIndex(),
911                                                T->isParameterPack(),
912                                                T->getName());
913  TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
914  NewTL.setNameLoc(TL.getNameLoc());
915  return Result;
916}
917
918/// \brief Perform substitution on the type T with a given set of template
919/// arguments.
920///
921/// This routine substitutes the given template arguments into the
922/// type T and produces the instantiated type.
923///
924/// \param T the type into which the template arguments will be
925/// substituted. If this type is not dependent, it will be returned
926/// immediately.
927///
928/// \param TemplateArgs the template arguments that will be
929/// substituted for the top-level template parameters within T.
930///
931/// \param Loc the location in the source code where this substitution
932/// is being performed. It will typically be the location of the
933/// declarator (if we're instantiating the type of some declaration)
934/// or the location of the type in the source code (if, e.g., we're
935/// instantiating the type of a cast expression).
936///
937/// \param Entity the name of the entity associated with a declaration
938/// being instantiated (if any). May be empty to indicate that there
939/// is no such entity (if, e.g., this is a type that occurs as part of
940/// a cast expression) or that the entity has no name (e.g., an
941/// unnamed function parameter).
942///
943/// \returns If the instantiation succeeds, the instantiated
944/// type. Otherwise, produces diagnostics and returns a NULL type.
945TypeSourceInfo *Sema::SubstType(TypeSourceInfo *T,
946                                const MultiLevelTemplateArgumentList &Args,
947                                SourceLocation Loc,
948                                DeclarationName Entity) {
949  assert(!ActiveTemplateInstantiations.empty() &&
950         "Cannot perform an instantiation without some context on the "
951         "instantiation stack");
952
953  if (!T->getType()->isDependentType() &&
954      !T->getType()->isVariablyModifiedType())
955    return T;
956
957  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
958  return Instantiator.TransformType(T);
959}
960
961/// Deprecated form of the above.
962QualType Sema::SubstType(QualType T,
963                         const MultiLevelTemplateArgumentList &TemplateArgs,
964                         SourceLocation Loc, DeclarationName Entity) {
965  assert(!ActiveTemplateInstantiations.empty() &&
966         "Cannot perform an instantiation without some context on the "
967         "instantiation stack");
968
969  // If T is not a dependent type or a variably-modified type, there
970  // is nothing to do.
971  if (!T->isDependentType() && !T->isVariablyModifiedType())
972    return T;
973
974  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
975  return Instantiator.TransformType(T);
976}
977
978static bool NeedsInstantiationAsFunctionType(TypeSourceInfo *T) {
979  if (T->getType()->isDependentType() || T->getType()->isVariablyModifiedType())
980    return true;
981
982  TypeLoc TL = T->getTypeLoc();
983  if (!isa<FunctionProtoTypeLoc>(TL))
984    return false;
985
986  FunctionProtoTypeLoc FP = cast<FunctionProtoTypeLoc>(TL);
987  for (unsigned I = 0, E = FP.getNumArgs(); I != E; ++I) {
988    ParmVarDecl *P = FP.getArg(I);
989
990    // TODO: currently we always rebuild expressions.  When we
991    // properly get lazier about this, we should use the same
992    // logic to avoid rebuilding prototypes here.
993    if (P->hasInit())
994      return true;
995  }
996
997  return false;
998}
999
1000/// A form of SubstType intended specifically for instantiating the
1001/// type of a FunctionDecl.  Its purpose is solely to force the
1002/// instantiation of default-argument expressions.
1003TypeSourceInfo *Sema::SubstFunctionDeclType(TypeSourceInfo *T,
1004                                const MultiLevelTemplateArgumentList &Args,
1005                                SourceLocation Loc,
1006                                DeclarationName Entity) {
1007  assert(!ActiveTemplateInstantiations.empty() &&
1008         "Cannot perform an instantiation without some context on the "
1009         "instantiation stack");
1010
1011  if (!NeedsInstantiationAsFunctionType(T))
1012    return T;
1013
1014  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1015
1016  TypeLocBuilder TLB;
1017
1018  TypeLoc TL = T->getTypeLoc();
1019  TLB.reserve(TL.getFullDataSize());
1020
1021  QualType Result = Instantiator.TransformType(TLB, TL, QualType());
1022  if (Result.isNull())
1023    return 0;
1024
1025  return TLB.getTypeSourceInfo(Context, Result);
1026}
1027
1028ParmVarDecl *Sema::SubstParmVarDecl(ParmVarDecl *OldParm,
1029                          const MultiLevelTemplateArgumentList &TemplateArgs) {
1030  TypeSourceInfo *OldDI = OldParm->getTypeSourceInfo();
1031  TypeSourceInfo *NewDI = SubstType(OldDI, TemplateArgs, OldParm->getLocation(),
1032                                    OldParm->getDeclName());
1033  if (!NewDI)
1034    return 0;
1035
1036  if (NewDI->getType()->isVoidType()) {
1037    Diag(OldParm->getLocation(), diag::err_param_with_void_type);
1038    return 0;
1039  }
1040
1041  ParmVarDecl *NewParm = CheckParameter(Context.getTranslationUnitDecl(),
1042                                        NewDI, NewDI->getType(),
1043                                        OldParm->getIdentifier(),
1044                                        OldParm->getLocation(),
1045                                        OldParm->getStorageClass(),
1046                                        OldParm->getStorageClassAsWritten());
1047  if (!NewParm)
1048    return 0;
1049
1050  // Mark the (new) default argument as uninstantiated (if any).
1051  if (OldParm->hasUninstantiatedDefaultArg()) {
1052    Expr *Arg = OldParm->getUninstantiatedDefaultArg();
1053    NewParm->setUninstantiatedDefaultArg(Arg);
1054  } else if (Expr *Arg = OldParm->getDefaultArg())
1055    NewParm->setUninstantiatedDefaultArg(Arg);
1056
1057  NewParm->setHasInheritedDefaultArg(OldParm->hasInheritedDefaultArg());
1058
1059  CurrentInstantiationScope->InstantiatedLocal(OldParm, NewParm);
1060  return NewParm;
1061}
1062
1063/// \brief Perform substitution on the base class specifiers of the
1064/// given class template specialization.
1065///
1066/// Produces a diagnostic and returns true on error, returns false and
1067/// attaches the instantiated base classes to the class template
1068/// specialization if successful.
1069bool
1070Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
1071                          CXXRecordDecl *Pattern,
1072                          const MultiLevelTemplateArgumentList &TemplateArgs) {
1073  bool Invalid = false;
1074  llvm::SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
1075  for (ClassTemplateSpecializationDecl::base_class_iterator
1076         Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
1077       Base != BaseEnd; ++Base) {
1078    if (!Base->getType()->isDependentType()) {
1079      const CXXRecordDecl *BaseDecl =
1080        cast<CXXRecordDecl>(Base->getType()->getAs<RecordType>()->getDecl());
1081
1082      // Make sure to set the attributes from the base.
1083      SetClassDeclAttributesFromBase(Instantiation, BaseDecl,
1084                                     Base->isVirtual());
1085
1086      InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(*Base));
1087      continue;
1088    }
1089
1090    QualType BaseType = SubstType(Base->getType(),
1091                                  TemplateArgs,
1092                                  Base->getSourceRange().getBegin(),
1093                                  DeclarationName());
1094    if (BaseType.isNull()) {
1095      Invalid = true;
1096      continue;
1097    }
1098
1099    if (CXXBaseSpecifier *InstantiatedBase
1100          = CheckBaseSpecifier(Instantiation,
1101                               Base->getSourceRange(),
1102                               Base->isVirtual(),
1103                               Base->getAccessSpecifierAsWritten(),
1104                               BaseType,
1105                               /*FIXME: Not totally accurate */
1106                               Base->getSourceRange().getBegin()))
1107      InstantiatedBases.push_back(InstantiatedBase);
1108    else
1109      Invalid = true;
1110  }
1111
1112  if (!Invalid &&
1113      AttachBaseSpecifiers(Instantiation, InstantiatedBases.data(),
1114                           InstantiatedBases.size()))
1115    Invalid = true;
1116
1117  return Invalid;
1118}
1119
1120/// \brief Instantiate the definition of a class from a given pattern.
1121///
1122/// \param PointOfInstantiation The point of instantiation within the
1123/// source code.
1124///
1125/// \param Instantiation is the declaration whose definition is being
1126/// instantiated. This will be either a class template specialization
1127/// or a member class of a class template specialization.
1128///
1129/// \param Pattern is the pattern from which the instantiation
1130/// occurs. This will be either the declaration of a class template or
1131/// the declaration of a member class of a class template.
1132///
1133/// \param TemplateArgs The template arguments to be substituted into
1134/// the pattern.
1135///
1136/// \param TSK the kind of implicit or explicit instantiation to perform.
1137///
1138/// \param Complain whether to complain if the class cannot be instantiated due
1139/// to the lack of a definition.
1140///
1141/// \returns true if an error occurred, false otherwise.
1142bool
1143Sema::InstantiateClass(SourceLocation PointOfInstantiation,
1144                       CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
1145                       const MultiLevelTemplateArgumentList &TemplateArgs,
1146                       TemplateSpecializationKind TSK,
1147                       bool Complain) {
1148  bool Invalid = false;
1149
1150  CXXRecordDecl *PatternDef
1151    = cast_or_null<CXXRecordDecl>(Pattern->getDefinition());
1152  if (!PatternDef) {
1153    if (!Complain) {
1154      // Say nothing
1155    } else if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
1156      Diag(PointOfInstantiation,
1157           diag::err_implicit_instantiate_member_undefined)
1158        << Context.getTypeDeclType(Instantiation);
1159      Diag(Pattern->getLocation(), diag::note_member_of_template_here);
1160    } else {
1161      Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
1162        << (TSK != TSK_ImplicitInstantiation)
1163        << Context.getTypeDeclType(Instantiation);
1164      Diag(Pattern->getLocation(), diag::note_template_decl_here);
1165    }
1166    return true;
1167  }
1168  Pattern = PatternDef;
1169
1170  // \brief Record the point of instantiation.
1171  if (MemberSpecializationInfo *MSInfo
1172        = Instantiation->getMemberSpecializationInfo()) {
1173    MSInfo->setTemplateSpecializationKind(TSK);
1174    MSInfo->setPointOfInstantiation(PointOfInstantiation);
1175  } else if (ClassTemplateSpecializationDecl *Spec
1176               = dyn_cast<ClassTemplateSpecializationDecl>(Instantiation)) {
1177    Spec->setTemplateSpecializationKind(TSK);
1178    Spec->setPointOfInstantiation(PointOfInstantiation);
1179  }
1180
1181  InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
1182  if (Inst)
1183    return true;
1184
1185  // Enter the scope of this instantiation. We don't use
1186  // PushDeclContext because we don't have a scope.
1187  ContextRAII SavedContext(*this, Instantiation);
1188  EnterExpressionEvaluationContext EvalContext(*this,
1189                                               Action::PotentiallyEvaluated);
1190
1191  // If this is an instantiation of a local class, merge this local
1192  // instantiation scope with the enclosing scope. Otherwise, every
1193  // instantiation of a class has its own local instantiation scope.
1194  bool MergeWithParentScope = !Instantiation->isDefinedOutsideFunctionOrMethod();
1195  Sema::LocalInstantiationScope Scope(*this, MergeWithParentScope);
1196
1197  // Start the definition of this instantiation.
1198  Instantiation->startDefinition();
1199
1200  Instantiation->setTagKind(Pattern->getTagKind());
1201
1202  // Do substitution on the base class specifiers.
1203  if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
1204    Invalid = true;
1205
1206  llvm::SmallVector<DeclPtrTy, 4> Fields;
1207  for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
1208         MemberEnd = Pattern->decls_end();
1209       Member != MemberEnd; ++Member) {
1210    Decl *NewMember = SubstDecl(*Member, Instantiation, TemplateArgs);
1211    if (NewMember) {
1212      if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember))
1213        Fields.push_back(DeclPtrTy::make(Field));
1214      else if (NewMember->isInvalidDecl())
1215        Invalid = true;
1216    } else {
1217      // FIXME: Eventually, a NULL return will mean that one of the
1218      // instantiations was a semantic disaster, and we'll want to set Invalid =
1219      // true. For now, we expect to skip some members that we can't yet handle.
1220    }
1221  }
1222
1223  // Finish checking fields.
1224  ActOnFields(0, Instantiation->getLocation(), DeclPtrTy::make(Instantiation),
1225              Fields.data(), Fields.size(), SourceLocation(), SourceLocation(),
1226              0);
1227  CheckCompletedCXXClass(Instantiation);
1228  if (Instantiation->isInvalidDecl())
1229    Invalid = true;
1230
1231  // Exit the scope of this instantiation.
1232  SavedContext.pop();
1233
1234  if (!Invalid) {
1235    Consumer.HandleTagDeclDefinition(Instantiation);
1236
1237    // Always emit the vtable for an explicit instantiation definition
1238    // of a polymorphic class template specialization.
1239    if (TSK == TSK_ExplicitInstantiationDefinition)
1240      MarkVTableUsed(PointOfInstantiation, Instantiation, true);
1241  }
1242
1243  return Invalid;
1244}
1245
1246bool
1247Sema::InstantiateClassTemplateSpecialization(
1248                           SourceLocation PointOfInstantiation,
1249                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
1250                           TemplateSpecializationKind TSK,
1251                           bool Complain) {
1252  // Perform the actual instantiation on the canonical declaration.
1253  ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
1254                                         ClassTemplateSpec->getCanonicalDecl());
1255
1256  // Check whether we have already instantiated or specialized this class
1257  // template specialization.
1258  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared) {
1259    if (ClassTemplateSpec->getSpecializationKind() ==
1260          TSK_ExplicitInstantiationDeclaration &&
1261        TSK == TSK_ExplicitInstantiationDefinition) {
1262      // An explicit instantiation definition follows an explicit instantiation
1263      // declaration (C++0x [temp.explicit]p10); go ahead and perform the
1264      // explicit instantiation.
1265      ClassTemplateSpec->setSpecializationKind(TSK);
1266
1267      // If this is an explicit instantiation definition, mark the
1268      // vtable as used.
1269      if (TSK == TSK_ExplicitInstantiationDefinition)
1270        MarkVTableUsed(PointOfInstantiation, ClassTemplateSpec, true);
1271
1272      return false;
1273    }
1274
1275    // We can only instantiate something that hasn't already been
1276    // instantiated or specialized. Fail without any diagnostics: our
1277    // caller will provide an error message.
1278    return true;
1279  }
1280
1281  if (ClassTemplateSpec->isInvalidDecl())
1282    return true;
1283
1284  ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
1285  CXXRecordDecl *Pattern = 0;
1286
1287  // C++ [temp.class.spec.match]p1:
1288  //   When a class template is used in a context that requires an
1289  //   instantiation of the class, it is necessary to determine
1290  //   whether the instantiation is to be generated using the primary
1291  //   template or one of the partial specializations. This is done by
1292  //   matching the template arguments of the class template
1293  //   specialization with the template argument lists of the partial
1294  //   specializations.
1295  typedef std::pair<ClassTemplatePartialSpecializationDecl *,
1296                    TemplateArgumentList *> MatchResult;
1297  llvm::SmallVector<MatchResult, 4> Matched;
1298  llvm::SmallVector<ClassTemplatePartialSpecializationDecl *, 4> PartialSpecs;
1299  Template->getPartialSpecializations(PartialSpecs);
1300  for (unsigned I = 0, N = PartialSpecs.size(); I != N; ++I) {
1301    ClassTemplatePartialSpecializationDecl *Partial = PartialSpecs[I];
1302    TemplateDeductionInfo Info(Context, PointOfInstantiation);
1303    if (TemplateDeductionResult Result
1304          = DeduceTemplateArguments(Partial,
1305                                    ClassTemplateSpec->getTemplateArgs(),
1306                                    Info)) {
1307      // FIXME: Store the failed-deduction information for use in
1308      // diagnostics, later.
1309      (void)Result;
1310    } else {
1311      Matched.push_back(std::make_pair(Partial, Info.take()));
1312    }
1313  }
1314
1315  if (Matched.size() >= 1) {
1316    llvm::SmallVector<MatchResult, 4>::iterator Best = Matched.begin();
1317    if (Matched.size() == 1) {
1318      //   -- If exactly one matching specialization is found, the
1319      //      instantiation is generated from that specialization.
1320      // We don't need to do anything for this.
1321    } else {
1322      //   -- If more than one matching specialization is found, the
1323      //      partial order rules (14.5.4.2) are used to determine
1324      //      whether one of the specializations is more specialized
1325      //      than the others. If none of the specializations is more
1326      //      specialized than all of the other matching
1327      //      specializations, then the use of the class template is
1328      //      ambiguous and the program is ill-formed.
1329      for (llvm::SmallVector<MatchResult, 4>::iterator P = Best + 1,
1330                                                    PEnd = Matched.end();
1331           P != PEnd; ++P) {
1332        if (getMoreSpecializedPartialSpecialization(P->first, Best->first,
1333                                                    PointOfInstantiation)
1334              == P->first)
1335          Best = P;
1336      }
1337
1338      // Determine if the best partial specialization is more specialized than
1339      // the others.
1340      bool Ambiguous = false;
1341      for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1342                                                    PEnd = Matched.end();
1343           P != PEnd; ++P) {
1344        if (P != Best &&
1345            getMoreSpecializedPartialSpecialization(P->first, Best->first,
1346                                                    PointOfInstantiation)
1347              != Best->first) {
1348          Ambiguous = true;
1349          break;
1350        }
1351      }
1352
1353      if (Ambiguous) {
1354        // Partial ordering did not produce a clear winner. Complain.
1355        ClassTemplateSpec->setInvalidDecl();
1356        Diag(PointOfInstantiation, diag::err_partial_spec_ordering_ambiguous)
1357          << ClassTemplateSpec;
1358
1359        // Print the matching partial specializations.
1360        for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1361                                                      PEnd = Matched.end();
1362             P != PEnd; ++P)
1363          Diag(P->first->getLocation(), diag::note_partial_spec_match)
1364            << getTemplateArgumentBindingsText(P->first->getTemplateParameters(),
1365                                               *P->second);
1366
1367        return true;
1368      }
1369    }
1370
1371    // Instantiate using the best class template partial specialization.
1372    ClassTemplatePartialSpecializationDecl *OrigPartialSpec = Best->first;
1373    while (OrigPartialSpec->getInstantiatedFromMember()) {
1374      // If we've found an explicit specialization of this class template,
1375      // stop here and use that as the pattern.
1376      if (OrigPartialSpec->isMemberSpecialization())
1377        break;
1378
1379      OrigPartialSpec = OrigPartialSpec->getInstantiatedFromMember();
1380    }
1381
1382    Pattern = OrigPartialSpec;
1383    ClassTemplateSpec->setInstantiationOf(Best->first, Best->second);
1384  } else {
1385    //   -- If no matches are found, the instantiation is generated
1386    //      from the primary template.
1387    ClassTemplateDecl *OrigTemplate = Template;
1388    while (OrigTemplate->getInstantiatedFromMemberTemplate()) {
1389      // If we've found an explicit specialization of this class template,
1390      // stop here and use that as the pattern.
1391      if (OrigTemplate->isMemberSpecialization())
1392        break;
1393
1394      OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
1395    }
1396
1397    Pattern = OrigTemplate->getTemplatedDecl();
1398  }
1399
1400  bool Result = InstantiateClass(PointOfInstantiation, ClassTemplateSpec,
1401                                 Pattern,
1402                                getTemplateInstantiationArgs(ClassTemplateSpec),
1403                                 TSK,
1404                                 Complain);
1405
1406  for (unsigned I = 0, N = Matched.size(); I != N; ++I) {
1407    // FIXME: Implement TemplateArgumentList::Destroy!
1408    //    if (Matched[I].first != Pattern)
1409    //      Matched[I].second->Destroy(Context);
1410  }
1411
1412  return Result;
1413}
1414
1415/// \brief Instantiates the definitions of all of the member
1416/// of the given class, which is an instantiation of a class template
1417/// or a member class of a template.
1418void
1419Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
1420                              CXXRecordDecl *Instantiation,
1421                        const MultiLevelTemplateArgumentList &TemplateArgs,
1422                              TemplateSpecializationKind TSK) {
1423  for (DeclContext::decl_iterator D = Instantiation->decls_begin(),
1424                               DEnd = Instantiation->decls_end();
1425       D != DEnd; ++D) {
1426    bool SuppressNew = false;
1427    if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
1428      if (FunctionDecl *Pattern
1429            = Function->getInstantiatedFromMemberFunction()) {
1430        MemberSpecializationInfo *MSInfo
1431          = Function->getMemberSpecializationInfo();
1432        assert(MSInfo && "No member specialization information?");
1433        if (MSInfo->getTemplateSpecializationKind()
1434                                                 == TSK_ExplicitSpecialization)
1435          continue;
1436
1437        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1438                                                   Function,
1439                                        MSInfo->getTemplateSpecializationKind(),
1440                                              MSInfo->getPointOfInstantiation(),
1441                                                   SuppressNew) ||
1442            SuppressNew)
1443          continue;
1444
1445        if (Function->getBody())
1446          continue;
1447
1448        if (TSK == TSK_ExplicitInstantiationDefinition) {
1449          // C++0x [temp.explicit]p8:
1450          //   An explicit instantiation definition that names a class template
1451          //   specialization explicitly instantiates the class template
1452          //   specialization and is only an explicit instantiation definition
1453          //   of members whose definition is visible at the point of
1454          //   instantiation.
1455          if (!Pattern->getBody())
1456            continue;
1457
1458          Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1459
1460          InstantiateFunctionDefinition(PointOfInstantiation, Function);
1461        } else {
1462          Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1463        }
1464      }
1465    } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
1466      if (Var->isStaticDataMember()) {
1467        MemberSpecializationInfo *MSInfo = Var->getMemberSpecializationInfo();
1468        assert(MSInfo && "No member specialization information?");
1469        if (MSInfo->getTemplateSpecializationKind()
1470                                                 == TSK_ExplicitSpecialization)
1471          continue;
1472
1473        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1474                                                   Var,
1475                                        MSInfo->getTemplateSpecializationKind(),
1476                                              MSInfo->getPointOfInstantiation(),
1477                                                   SuppressNew) ||
1478            SuppressNew)
1479          continue;
1480
1481        if (TSK == TSK_ExplicitInstantiationDefinition) {
1482          // C++0x [temp.explicit]p8:
1483          //   An explicit instantiation definition that names a class template
1484          //   specialization explicitly instantiates the class template
1485          //   specialization and is only an explicit instantiation definition
1486          //   of members whose definition is visible at the point of
1487          //   instantiation.
1488          if (!Var->getInstantiatedFromStaticDataMember()
1489                                                     ->getOutOfLineDefinition())
1490            continue;
1491
1492          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1493          InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
1494        } else {
1495          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1496        }
1497      }
1498    } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
1499      // Always skip the injected-class-name, along with any
1500      // redeclarations of nested classes, since both would cause us
1501      // to try to instantiate the members of a class twice.
1502      if (Record->isInjectedClassName() || Record->getPreviousDeclaration())
1503        continue;
1504
1505      MemberSpecializationInfo *MSInfo = Record->getMemberSpecializationInfo();
1506      assert(MSInfo && "No member specialization information?");
1507
1508      if (MSInfo->getTemplateSpecializationKind()
1509                                                == TSK_ExplicitSpecialization)
1510        continue;
1511
1512      if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1513                                                 Record,
1514                                        MSInfo->getTemplateSpecializationKind(),
1515                                              MSInfo->getPointOfInstantiation(),
1516                                                 SuppressNew) ||
1517          SuppressNew)
1518        continue;
1519
1520      CXXRecordDecl *Pattern = Record->getInstantiatedFromMemberClass();
1521      assert(Pattern && "Missing instantiated-from-template information");
1522
1523      if (!Record->getDefinition()) {
1524        if (!Pattern->getDefinition()) {
1525          // C++0x [temp.explicit]p8:
1526          //   An explicit instantiation definition that names a class template
1527          //   specialization explicitly instantiates the class template
1528          //   specialization and is only an explicit instantiation definition
1529          //   of members whose definition is visible at the point of
1530          //   instantiation.
1531          if (TSK == TSK_ExplicitInstantiationDeclaration) {
1532            MSInfo->setTemplateSpecializationKind(TSK);
1533            MSInfo->setPointOfInstantiation(PointOfInstantiation);
1534          }
1535
1536          continue;
1537        }
1538
1539        InstantiateClass(PointOfInstantiation, Record, Pattern,
1540                         TemplateArgs,
1541                         TSK);
1542      }
1543
1544      Pattern = cast_or_null<CXXRecordDecl>(Record->getDefinition());
1545      if (Pattern)
1546        InstantiateClassMembers(PointOfInstantiation, Pattern, TemplateArgs,
1547                                TSK);
1548    }
1549  }
1550}
1551
1552/// \brief Instantiate the definitions of all of the members of the
1553/// given class template specialization, which was named as part of an
1554/// explicit instantiation.
1555void
1556Sema::InstantiateClassTemplateSpecializationMembers(
1557                                           SourceLocation PointOfInstantiation,
1558                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
1559                                               TemplateSpecializationKind TSK) {
1560  // C++0x [temp.explicit]p7:
1561  //   An explicit instantiation that names a class template
1562  //   specialization is an explicit instantion of the same kind
1563  //   (declaration or definition) of each of its members (not
1564  //   including members inherited from base classes) that has not
1565  //   been previously explicitly specialized in the translation unit
1566  //   containing the explicit instantiation, except as described
1567  //   below.
1568  InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
1569                          getTemplateInstantiationArgs(ClassTemplateSpec),
1570                          TSK);
1571}
1572
1573Sema::OwningStmtResult
1574Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
1575  if (!S)
1576    return Owned(S);
1577
1578  TemplateInstantiator Instantiator(*this, TemplateArgs,
1579                                    SourceLocation(),
1580                                    DeclarationName());
1581  return Instantiator.TransformStmt(S);
1582}
1583
1584Sema::OwningExprResult
1585Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
1586  if (!E)
1587    return Owned(E);
1588
1589  TemplateInstantiator Instantiator(*this, TemplateArgs,
1590                                    SourceLocation(),
1591                                    DeclarationName());
1592  return Instantiator.TransformExpr(E);
1593}
1594
1595/// \brief Do template substitution on a nested-name-specifier.
1596NestedNameSpecifier *
1597Sema::SubstNestedNameSpecifier(NestedNameSpecifier *NNS,
1598                               SourceRange Range,
1599                         const MultiLevelTemplateArgumentList &TemplateArgs) {
1600  TemplateInstantiator Instantiator(*this, TemplateArgs, Range.getBegin(),
1601                                    DeclarationName());
1602  return Instantiator.TransformNestedNameSpecifier(NNS, Range);
1603}
1604
1605TemplateName
1606Sema::SubstTemplateName(TemplateName Name, SourceLocation Loc,
1607                        const MultiLevelTemplateArgumentList &TemplateArgs) {
1608  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
1609                                    DeclarationName());
1610  return Instantiator.TransformTemplateName(Name);
1611}
1612
1613bool Sema::Subst(const TemplateArgumentLoc &Input, TemplateArgumentLoc &Output,
1614                 const MultiLevelTemplateArgumentList &TemplateArgs) {
1615  TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
1616                                    DeclarationName());
1617
1618  return Instantiator.TransformTemplateArgument(Input, Output);
1619}
1620
1621Decl *Sema::LocalInstantiationScope::getInstantiationOf(const Decl *D) {
1622  for (LocalInstantiationScope *Current = this; Current;
1623       Current = Current->Outer) {
1624    // Check if we found something within this scope.
1625    llvm::DenseMap<const Decl *, Decl *>::iterator Found
1626      = Current->LocalDecls.find(D);
1627    if (Found != Current->LocalDecls.end())
1628      return Found->second;
1629
1630    // If we aren't combined with our outer scope, we're done.
1631    if (!Current->CombineWithOuterScope)
1632      break;
1633  }
1634
1635  assert(D->isInvalidDecl() &&
1636         "declaration was not instantiated in this scope!");
1637  return 0;
1638}
1639
1640void Sema::LocalInstantiationScope::InstantiatedLocal(const Decl *D,
1641                                                      Decl *Inst) {
1642  Decl *&Stored = LocalDecls[D];
1643  assert((!Stored || Stored == Inst)&& "Already instantiated this local");
1644  Stored = Inst;
1645}
1646