SemaTemplateInstantiate.cpp revision ab1f1819386bd718899582eb6426b2619b11e2cf 
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}
625
626bool TemplateInstantiator::AlreadyTransformed(QualType T) {
627  if (T.isNull())
628    return true;
629
630  if (T->isDependentType())
631    return false;
632
633  getSema().MarkDeclarationsReferencedInType(Loc, T);
634  return true;
635}
636
637Decl *TemplateInstantiator::TransformDecl(SourceLocation Loc, Decl *D) {
638  if (!D)
639    return 0;
640
641  if (TemplateTemplateParmDecl *TTP = dyn_cast<TemplateTemplateParmDecl>(D)) {
642    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
643      // If the corresponding template argument is NULL or non-existent, it's
644      // because we are performing instantiation from explicitly-specified
645      // template arguments in a function template, but there were some
646      // arguments left unspecified.
647      if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(),
648                                            TTP->getPosition()))
649        return D;
650
651      TemplateName Template
652        = TemplateArgs(TTP->getDepth(), TTP->getPosition()).getAsTemplate();
653      assert(!Template.isNull() && Template.getAsTemplateDecl() &&
654             "Wrong kind of template template argument");
655      return Template.getAsTemplateDecl();
656    }
657
658    // Fall through to find the instantiated declaration for this template
659    // template parameter.
660  }
661
662  return SemaRef.FindInstantiatedDecl(Loc, cast<NamedDecl>(D), TemplateArgs);
663}
664
665Decl *TemplateInstantiator::TransformDefinition(SourceLocation Loc, Decl *D) {
666  Decl *Inst = getSema().SubstDecl(D, getSema().CurContext, TemplateArgs);
667  if (!Inst)
668    return 0;
669
670  getSema().CurrentInstantiationScope->InstantiatedLocal(D, Inst);
671  return Inst;
672}
673
674NamedDecl *
675TemplateInstantiator::TransformFirstQualifierInScope(NamedDecl *D,
676                                                     SourceLocation Loc) {
677  // If the first part of the nested-name-specifier was a template type
678  // parameter, instantiate that type parameter down to a tag type.
679  if (TemplateTypeParmDecl *TTPD = dyn_cast_or_null<TemplateTypeParmDecl>(D)) {
680    const TemplateTypeParmType *TTP
681      = cast<TemplateTypeParmType>(getSema().Context.getTypeDeclType(TTPD));
682    if (TTP->getDepth() < TemplateArgs.getNumLevels()) {
683      QualType T = TemplateArgs(TTP->getDepth(), TTP->getIndex()).getAsType();
684      if (T.isNull())
685        return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
686
687      if (const TagType *Tag = T->getAs<TagType>())
688        return Tag->getDecl();
689
690      // The resulting type is not a tag; complain.
691      getSema().Diag(Loc, diag::err_nested_name_spec_non_tag) << T;
692      return 0;
693    }
694  }
695
696  return cast_or_null<NamedDecl>(TransformDecl(Loc, D));
697}
698
699VarDecl *
700TemplateInstantiator::RebuildExceptionDecl(VarDecl *ExceptionDecl,
701                                           QualType T,
702                                           TypeSourceInfo *Declarator,
703                                           IdentifierInfo *Name,
704                                           SourceLocation Loc,
705                                           SourceRange TypeRange) {
706  VarDecl *Var = inherited::RebuildExceptionDecl(ExceptionDecl, T, Declarator,
707                                                 Name, Loc, TypeRange);
708  if (Var)
709    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
710  return Var;
711}
712
713VarDecl *TemplateInstantiator::RebuildObjCExceptionDecl(VarDecl *ExceptionDecl,
714                                                        TypeSourceInfo *TSInfo,
715                                                        QualType T) {
716  VarDecl *Var = inherited::RebuildObjCExceptionDecl(ExceptionDecl, TSInfo, T);
717  if (Var)
718    getSema().CurrentInstantiationScope->InstantiatedLocal(ExceptionDecl, Var);
719  return Var;
720}
721
722QualType
723TemplateInstantiator::RebuildElaboratedType(ElaboratedTypeKeyword Keyword,
724                                            NestedNameSpecifier *NNS,
725                                            QualType T) {
726  if (const TagType *TT = T->getAs<TagType>()) {
727    TagDecl* TD = TT->getDecl();
728
729    // FIXME: this location is very wrong;  we really need typelocs.
730    SourceLocation TagLocation = TD->getTagKeywordLoc();
731
732    // FIXME: type might be anonymous.
733    IdentifierInfo *Id = TD->getIdentifier();
734
735    // TODO: should we even warn on struct/class mismatches for this?  Seems
736    // like it's likely to produce a lot of spurious errors.
737    if (Keyword != ETK_None && Keyword != ETK_Typename) {
738      TagTypeKind Kind = TypeWithKeyword::getTagTypeKindForKeyword(Keyword);
739      if (!SemaRef.isAcceptableTagRedeclaration(TD, Kind, TagLocation, *Id)) {
740        SemaRef.Diag(TagLocation, diag::err_use_with_wrong_tag)
741          << Id
742          << FixItHint::CreateReplacement(SourceRange(TagLocation),
743                                          TD->getKindName());
744        SemaRef.Diag(TD->getLocation(), diag::note_previous_use);
745      }
746    }
747  }
748
749  return TreeTransform<TemplateInstantiator>::RebuildElaboratedType(Keyword,
750                                                                    NNS, T);
751}
752
753Sema::OwningExprResult
754TemplateInstantiator::TransformPredefinedExpr(PredefinedExpr *E) {
755  if (!E->isTypeDependent())
756    return SemaRef.Owned(E->Retain());
757
758  FunctionDecl *currentDecl = getSema().getCurFunctionDecl();
759  assert(currentDecl && "Must have current function declaration when "
760                        "instantiating.");
761
762  PredefinedExpr::IdentType IT = E->getIdentType();
763
764  unsigned Length = PredefinedExpr::ComputeName(IT, currentDecl).length();
765
766  llvm::APInt LengthI(32, Length + 1);
767  QualType ResTy = getSema().Context.CharTy.withConst();
768  ResTy = getSema().Context.getConstantArrayType(ResTy, LengthI,
769                                                 ArrayType::Normal, 0);
770  PredefinedExpr *PE =
771    new (getSema().Context) PredefinedExpr(E->getLocation(), ResTy, IT);
772  return getSema().Owned(PE);
773}
774
775Sema::OwningExprResult
776TemplateInstantiator::TransformTemplateParmRefExpr(DeclRefExpr *E,
777                                               NonTypeTemplateParmDecl *NTTP) {
778  // If the corresponding template argument is NULL or non-existent, it's
779  // because we are performing instantiation from explicitly-specified
780  // template arguments in a function template, but there were some
781  // arguments left unspecified.
782  if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(),
783                                        NTTP->getPosition()))
784    return SemaRef.Owned(E->Retain());
785
786  const TemplateArgument &Arg = TemplateArgs(NTTP->getDepth(),
787                                             NTTP->getPosition());
788
789  // The template argument itself might be an expression, in which
790  // case we just return that expression.
791  if (Arg.getKind() == TemplateArgument::Expression)
792    return SemaRef.Owned(Arg.getAsExpr()->Retain());
793
794  if (Arg.getKind() == TemplateArgument::Declaration) {
795    ValueDecl *VD = cast<ValueDecl>(Arg.getAsDecl());
796
797    // Find the instantiation of the template argument.  This is
798    // required for nested templates.
799    VD = cast_or_null<ValueDecl>(
800                            getSema().FindInstantiatedDecl(E->getLocation(),
801                                                           VD, TemplateArgs));
802    if (!VD)
803      return SemaRef.ExprError();
804
805    // Derive the type we want the substituted decl to have.  This had
806    // better be non-dependent, or these checks will have serious problems.
807    QualType TargetType = SemaRef.SubstType(NTTP->getType(), TemplateArgs,
808                                            E->getLocation(),
809                                            DeclarationName());
810    assert(!TargetType.isNull() && "type substitution failed for param type");
811    assert(!TargetType->isDependentType() && "param type still dependent");
812    return SemaRef.BuildExpressionFromDeclTemplateArgument(Arg,
813                                                           TargetType,
814                                                           E->getLocation());
815  }
816
817  return SemaRef.BuildExpressionFromIntegralTemplateArgument(Arg,
818                                                E->getSourceRange().getBegin());
819}
820
821
822Sema::OwningExprResult
823TemplateInstantiator::TransformDeclRefExpr(DeclRefExpr *E) {
824  NamedDecl *D = E->getDecl();
825  if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D)) {
826    if (NTTP->getDepth() < TemplateArgs.getNumLevels())
827      return TransformTemplateParmRefExpr(E, NTTP);
828
829    // We have a non-type template parameter that isn't fully substituted;
830    // FindInstantiatedDecl will find it in the local instantiation scope.
831  }
832
833  return TreeTransform<TemplateInstantiator>::TransformDeclRefExpr(E);
834}
835
836Sema::OwningExprResult TemplateInstantiator::TransformCXXDefaultArgExpr(
837    CXXDefaultArgExpr *E) {
838  assert(!cast<FunctionDecl>(E->getParam()->getDeclContext())->
839             getDescribedFunctionTemplate() &&
840         "Default arg expressions are never formed in dependent cases.");
841  return SemaRef.BuildCXXDefaultArgExpr(E->getUsedLocation(),
842                           cast<FunctionDecl>(E->getParam()->getDeclContext()),
843                                        E->getParam());
844}
845
846QualType TemplateInstantiator::TransformFunctionProtoType(TypeLocBuilder &TLB,
847                                                        FunctionProtoTypeLoc TL,
848                                                          QualType ObjectType) {
849  // We need a local instantiation scope for this function prototype.
850  Sema::LocalInstantiationScope Scope(SemaRef, /*CombineWithOuterScope=*/true);
851  return inherited::TransformFunctionProtoType(TLB, TL, ObjectType);
852}
853
854ParmVarDecl *
855TemplateInstantiator::TransformFunctionTypeParam(ParmVarDecl *OldParm) {
856  return SemaRef.SubstParmVarDecl(OldParm, TemplateArgs);
857}
858
859QualType
860TemplateInstantiator::TransformTemplateTypeParmType(TypeLocBuilder &TLB,
861                                                TemplateTypeParmTypeLoc TL,
862                                                    QualType ObjectType) {
863  TemplateTypeParmType *T = TL.getTypePtr();
864  if (T->getDepth() < TemplateArgs.getNumLevels()) {
865    // Replace the template type parameter with its corresponding
866    // template argument.
867
868    // If the corresponding template argument is NULL or doesn't exist, it's
869    // because we are performing instantiation from explicitly-specified
870    // template arguments in a function template class, but there were some
871    // arguments left unspecified.
872    if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex())) {
873      TemplateTypeParmTypeLoc NewTL
874        = TLB.push<TemplateTypeParmTypeLoc>(TL.getType());
875      NewTL.setNameLoc(TL.getNameLoc());
876      return TL.getType();
877    }
878
879    assert(TemplateArgs(T->getDepth(), T->getIndex()).getKind()
880             == TemplateArgument::Type &&
881           "Template argument kind mismatch");
882
883    QualType Replacement
884      = TemplateArgs(T->getDepth(), T->getIndex()).getAsType();
885
886    // TODO: only do this uniquing once, at the start of instantiation.
887    QualType Result
888      = getSema().Context.getSubstTemplateTypeParmType(T, Replacement);
889    SubstTemplateTypeParmTypeLoc NewTL
890      = TLB.push<SubstTemplateTypeParmTypeLoc>(Result);
891    NewTL.setNameLoc(TL.getNameLoc());
892    return Result;
893  }
894
895  // The template type parameter comes from an inner template (e.g.,
896  // the template parameter list of a member template inside the
897  // template we are instantiating). Create a new template type
898  // parameter with the template "level" reduced by one.
899  QualType Result
900    = getSema().Context.getTemplateTypeParmType(T->getDepth()
901                                                 - TemplateArgs.getNumLevels(),
902                                                T->getIndex(),
903                                                T->isParameterPack(),
904                                                T->getName());
905  TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
906  NewTL.setNameLoc(TL.getNameLoc());
907  return Result;
908}
909
910/// \brief Perform substitution on the type T with a given set of template
911/// arguments.
912///
913/// This routine substitutes the given template arguments into the
914/// type T and produces the instantiated type.
915///
916/// \param T the type into which the template arguments will be
917/// substituted. If this type is not dependent, it will be returned
918/// immediately.
919///
920/// \param TemplateArgs the template arguments that will be
921/// substituted for the top-level template parameters within T.
922///
923/// \param Loc the location in the source code where this substitution
924/// is being performed. It will typically be the location of the
925/// declarator (if we're instantiating the type of some declaration)
926/// or the location of the type in the source code (if, e.g., we're
927/// instantiating the type of a cast expression).
928///
929/// \param Entity the name of the entity associated with a declaration
930/// being instantiated (if any). May be empty to indicate that there
931/// is no such entity (if, e.g., this is a type that occurs as part of
932/// a cast expression) or that the entity has no name (e.g., an
933/// unnamed function parameter).
934///
935/// \returns If the instantiation succeeds, the instantiated
936/// type. Otherwise, produces diagnostics and returns a NULL type.
937TypeSourceInfo *Sema::SubstType(TypeSourceInfo *T,
938                                const MultiLevelTemplateArgumentList &Args,
939                                SourceLocation Loc,
940                                DeclarationName Entity) {
941  assert(!ActiveTemplateInstantiations.empty() &&
942         "Cannot perform an instantiation without some context on the "
943         "instantiation stack");
944
945  if (!T->getType()->isDependentType())
946    return T;
947
948  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
949  return Instantiator.TransformType(T);
950}
951
952/// Deprecated form of the above.
953QualType Sema::SubstType(QualType T,
954                         const MultiLevelTemplateArgumentList &TemplateArgs,
955                         SourceLocation Loc, DeclarationName Entity) {
956  assert(!ActiveTemplateInstantiations.empty() &&
957         "Cannot perform an instantiation without some context on the "
958         "instantiation stack");
959
960  // If T is not a dependent type, there is nothing to do.
961  if (!T->isDependentType())
962    return T;
963
964  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc, Entity);
965  return Instantiator.TransformType(T);
966}
967
968static bool NeedsInstantiationAsFunctionType(TypeSourceInfo *T) {
969  if (T->getType()->isDependentType())
970    return true;
971
972  TypeLoc TL = T->getTypeLoc();
973  if (!isa<FunctionProtoTypeLoc>(TL))
974    return false;
975
976  FunctionProtoTypeLoc FP = cast<FunctionProtoTypeLoc>(TL);
977  for (unsigned I = 0, E = FP.getNumArgs(); I != E; ++I) {
978    ParmVarDecl *P = FP.getArg(I);
979
980    // TODO: currently we always rebuild expressions.  When we
981    // properly get lazier about this, we should use the same
982    // logic to avoid rebuilding prototypes here.
983    if (P->hasInit())
984      return true;
985  }
986
987  return false;
988}
989
990/// A form of SubstType intended specifically for instantiating the
991/// type of a FunctionDecl.  Its purpose is solely to force the
992/// instantiation of default-argument expressions.
993TypeSourceInfo *Sema::SubstFunctionDeclType(TypeSourceInfo *T,
994                                const MultiLevelTemplateArgumentList &Args,
995                                SourceLocation Loc,
996                                DeclarationName Entity) {
997  assert(!ActiveTemplateInstantiations.empty() &&
998         "Cannot perform an instantiation without some context on the "
999         "instantiation stack");
1000
1001  if (!NeedsInstantiationAsFunctionType(T))
1002    return T;
1003
1004  TemplateInstantiator Instantiator(*this, Args, Loc, Entity);
1005
1006  TypeLocBuilder TLB;
1007
1008  TypeLoc TL = T->getTypeLoc();
1009  TLB.reserve(TL.getFullDataSize());
1010
1011  QualType Result = Instantiator.TransformType(TLB, TL, QualType());
1012  if (Result.isNull())
1013    return 0;
1014
1015  return TLB.getTypeSourceInfo(Context, Result);
1016}
1017
1018ParmVarDecl *Sema::SubstParmVarDecl(ParmVarDecl *OldParm,
1019                          const MultiLevelTemplateArgumentList &TemplateArgs) {
1020  TypeSourceInfo *OldDI = OldParm->getTypeSourceInfo();
1021  TypeSourceInfo *NewDI = SubstType(OldDI, TemplateArgs, OldParm->getLocation(),
1022                                    OldParm->getDeclName());
1023  if (!NewDI)
1024    return 0;
1025
1026  if (NewDI->getType()->isVoidType()) {
1027    Diag(OldParm->getLocation(), diag::err_param_with_void_type);
1028    return 0;
1029  }
1030
1031  ParmVarDecl *NewParm = CheckParameter(Context.getTranslationUnitDecl(),
1032                                        NewDI, NewDI->getType(),
1033                                        OldParm->getIdentifier(),
1034                                        OldParm->getLocation(),
1035                                        OldParm->getStorageClass(),
1036                                        OldParm->getStorageClassAsWritten());
1037  if (!NewParm)
1038    return 0;
1039
1040  // Mark the (new) default argument as uninstantiated (if any).
1041  if (OldParm->hasUninstantiatedDefaultArg()) {
1042    Expr *Arg = OldParm->getUninstantiatedDefaultArg();
1043    NewParm->setUninstantiatedDefaultArg(Arg);
1044  } else if (Expr *Arg = OldParm->getDefaultArg())
1045    NewParm->setUninstantiatedDefaultArg(Arg);
1046
1047  NewParm->setHasInheritedDefaultArg(OldParm->hasInheritedDefaultArg());
1048
1049  CurrentInstantiationScope->InstantiatedLocal(OldParm, NewParm);
1050  return NewParm;
1051}
1052
1053/// \brief Perform substitution on the base class specifiers of the
1054/// given class template specialization.
1055///
1056/// Produces a diagnostic and returns true on error, returns false and
1057/// attaches the instantiated base classes to the class template
1058/// specialization if successful.
1059bool
1060Sema::SubstBaseSpecifiers(CXXRecordDecl *Instantiation,
1061                          CXXRecordDecl *Pattern,
1062                          const MultiLevelTemplateArgumentList &TemplateArgs) {
1063  bool Invalid = false;
1064  llvm::SmallVector<CXXBaseSpecifier*, 4> InstantiatedBases;
1065  for (ClassTemplateSpecializationDecl::base_class_iterator
1066         Base = Pattern->bases_begin(), BaseEnd = Pattern->bases_end();
1067       Base != BaseEnd; ++Base) {
1068    if (!Base->getType()->isDependentType()) {
1069      const CXXRecordDecl *BaseDecl =
1070        cast<CXXRecordDecl>(Base->getType()->getAs<RecordType>()->getDecl());
1071
1072      // Make sure to set the attributes from the base.
1073      SetClassDeclAttributesFromBase(Instantiation, BaseDecl,
1074                                     Base->isVirtual());
1075
1076      InstantiatedBases.push_back(new (Context) CXXBaseSpecifier(*Base));
1077      continue;
1078    }
1079
1080    QualType BaseType = SubstType(Base->getType(),
1081                                  TemplateArgs,
1082                                  Base->getSourceRange().getBegin(),
1083                                  DeclarationName());
1084    if (BaseType.isNull()) {
1085      Invalid = true;
1086      continue;
1087    }
1088
1089    if (CXXBaseSpecifier *InstantiatedBase
1090          = CheckBaseSpecifier(Instantiation,
1091                               Base->getSourceRange(),
1092                               Base->isVirtual(),
1093                               Base->getAccessSpecifierAsWritten(),
1094                               BaseType,
1095                               /*FIXME: Not totally accurate */
1096                               Base->getSourceRange().getBegin()))
1097      InstantiatedBases.push_back(InstantiatedBase);
1098    else
1099      Invalid = true;
1100  }
1101
1102  if (!Invalid &&
1103      AttachBaseSpecifiers(Instantiation, InstantiatedBases.data(),
1104                           InstantiatedBases.size()))
1105    Invalid = true;
1106
1107  return Invalid;
1108}
1109
1110/// \brief Instantiate the definition of a class from a given pattern.
1111///
1112/// \param PointOfInstantiation The point of instantiation within the
1113/// source code.
1114///
1115/// \param Instantiation is the declaration whose definition is being
1116/// instantiated. This will be either a class template specialization
1117/// or a member class of a class template specialization.
1118///
1119/// \param Pattern is the pattern from which the instantiation
1120/// occurs. This will be either the declaration of a class template or
1121/// the declaration of a member class of a class template.
1122///
1123/// \param TemplateArgs The template arguments to be substituted into
1124/// the pattern.
1125///
1126/// \param TSK the kind of implicit or explicit instantiation to perform.
1127///
1128/// \param Complain whether to complain if the class cannot be instantiated due
1129/// to the lack of a definition.
1130///
1131/// \returns true if an error occurred, false otherwise.
1132bool
1133Sema::InstantiateClass(SourceLocation PointOfInstantiation,
1134                       CXXRecordDecl *Instantiation, CXXRecordDecl *Pattern,
1135                       const MultiLevelTemplateArgumentList &TemplateArgs,
1136                       TemplateSpecializationKind TSK,
1137                       bool Complain) {
1138  bool Invalid = false;
1139
1140  CXXRecordDecl *PatternDef
1141    = cast_or_null<CXXRecordDecl>(Pattern->getDefinition());
1142  if (!PatternDef) {
1143    if (!Complain) {
1144      // Say nothing
1145    } else if (Pattern == Instantiation->getInstantiatedFromMemberClass()) {
1146      Diag(PointOfInstantiation,
1147           diag::err_implicit_instantiate_member_undefined)
1148        << Context.getTypeDeclType(Instantiation);
1149      Diag(Pattern->getLocation(), diag::note_member_of_template_here);
1150    } else {
1151      Diag(PointOfInstantiation, diag::err_template_instantiate_undefined)
1152        << (TSK != TSK_ImplicitInstantiation)
1153        << Context.getTypeDeclType(Instantiation);
1154      Diag(Pattern->getLocation(), diag::note_template_decl_here);
1155    }
1156    return true;
1157  }
1158  Pattern = PatternDef;
1159
1160  // \brief Record the point of instantiation.
1161  if (MemberSpecializationInfo *MSInfo
1162        = Instantiation->getMemberSpecializationInfo()) {
1163    MSInfo->setTemplateSpecializationKind(TSK);
1164    MSInfo->setPointOfInstantiation(PointOfInstantiation);
1165  } else if (ClassTemplateSpecializationDecl *Spec
1166               = dyn_cast<ClassTemplateSpecializationDecl>(Instantiation)) {
1167    Spec->setTemplateSpecializationKind(TSK);
1168    Spec->setPointOfInstantiation(PointOfInstantiation);
1169  }
1170
1171  InstantiatingTemplate Inst(*this, PointOfInstantiation, Instantiation);
1172  if (Inst)
1173    return true;
1174
1175  // Enter the scope of this instantiation. We don't use
1176  // PushDeclContext because we don't have a scope.
1177  ContextRAII SavedContext(*this, Instantiation);
1178
1179  // If this is an instantiation of a local class, merge this local
1180  // instantiation scope with the enclosing scope. Otherwise, every
1181  // instantiation of a class has its own local instantiation scope.
1182  bool MergeWithParentScope = !Instantiation->isDefinedOutsideFunctionOrMethod();
1183  Sema::LocalInstantiationScope Scope(*this, MergeWithParentScope);
1184
1185  // Start the definition of this instantiation.
1186  Instantiation->startDefinition();
1187
1188  Instantiation->setTagKind(Pattern->getTagKind());
1189
1190  // Do substitution on the base class specifiers.
1191  if (SubstBaseSpecifiers(Instantiation, Pattern, TemplateArgs))
1192    Invalid = true;
1193
1194  llvm::SmallVector<DeclPtrTy, 4> Fields;
1195  for (RecordDecl::decl_iterator Member = Pattern->decls_begin(),
1196         MemberEnd = Pattern->decls_end();
1197       Member != MemberEnd; ++Member) {
1198    Decl *NewMember = SubstDecl(*Member, Instantiation, TemplateArgs);
1199    if (NewMember) {
1200      if (FieldDecl *Field = dyn_cast<FieldDecl>(NewMember))
1201        Fields.push_back(DeclPtrTy::make(Field));
1202      else if (NewMember->isInvalidDecl())
1203        Invalid = true;
1204    } else {
1205      // FIXME: Eventually, a NULL return will mean that one of the
1206      // instantiations was a semantic disaster, and we'll want to set Invalid =
1207      // true. For now, we expect to skip some members that we can't yet handle.
1208    }
1209  }
1210
1211  // Finish checking fields.
1212  ActOnFields(0, Instantiation->getLocation(), DeclPtrTy::make(Instantiation),
1213              Fields.data(), Fields.size(), SourceLocation(), SourceLocation(),
1214              0);
1215  CheckCompletedCXXClass(/*Scope=*/0, Instantiation);
1216  if (Instantiation->isInvalidDecl())
1217    Invalid = true;
1218
1219  // Exit the scope of this instantiation.
1220  SavedContext.pop();
1221
1222  // If this is a polymorphic C++ class without a key function, we'll
1223  // have to mark all of the virtual members to allow emission of a vtable
1224  // in this translation unit.
1225  if (Instantiation->isDynamicClass() &&
1226      !Context.getKeyFunction(Instantiation)) {
1227    // Local classes need to have their methods instantiated immediately in
1228    // order to have the correct instantiation scope.
1229    if (Instantiation->isLocalClass()) {
1230      MarkVirtualMembersReferenced(PointOfInstantiation,
1231                                   Instantiation);
1232    } else {
1233      ClassesWithUnmarkedVirtualMembers.push_back(std::make_pair(Instantiation,
1234                                                       PointOfInstantiation));
1235    }
1236  }
1237
1238  if (!Invalid)
1239    Consumer.HandleTagDeclDefinition(Instantiation);
1240
1241  return Invalid;
1242}
1243
1244bool
1245Sema::InstantiateClassTemplateSpecialization(
1246                           SourceLocation PointOfInstantiation,
1247                           ClassTemplateSpecializationDecl *ClassTemplateSpec,
1248                           TemplateSpecializationKind TSK,
1249                           bool Complain) {
1250  // Perform the actual instantiation on the canonical declaration.
1251  ClassTemplateSpec = cast<ClassTemplateSpecializationDecl>(
1252                                         ClassTemplateSpec->getCanonicalDecl());
1253
1254  // Check whether we have already instantiated or specialized this class
1255  // template specialization.
1256  if (ClassTemplateSpec->getSpecializationKind() != TSK_Undeclared) {
1257    if (ClassTemplateSpec->getSpecializationKind() ==
1258          TSK_ExplicitInstantiationDeclaration &&
1259        TSK == TSK_ExplicitInstantiationDefinition) {
1260      // An explicit instantiation definition follows an explicit instantiation
1261      // declaration (C++0x [temp.explicit]p10); go ahead and perform the
1262      // explicit instantiation.
1263      ClassTemplateSpec->setSpecializationKind(TSK);
1264      return false;
1265    }
1266
1267    // We can only instantiate something that hasn't already been
1268    // instantiated or specialized. Fail without any diagnostics: our
1269    // caller will provide an error message.
1270    return true;
1271  }
1272
1273  if (ClassTemplateSpec->isInvalidDecl())
1274    return true;
1275
1276  ClassTemplateDecl *Template = ClassTemplateSpec->getSpecializedTemplate();
1277  CXXRecordDecl *Pattern = 0;
1278
1279  // C++ [temp.class.spec.match]p1:
1280  //   When a class template is used in a context that requires an
1281  //   instantiation of the class, it is necessary to determine
1282  //   whether the instantiation is to be generated using the primary
1283  //   template or one of the partial specializations. This is done by
1284  //   matching the template arguments of the class template
1285  //   specialization with the template argument lists of the partial
1286  //   specializations.
1287  typedef std::pair<ClassTemplatePartialSpecializationDecl *,
1288                    TemplateArgumentList *> MatchResult;
1289  llvm::SmallVector<MatchResult, 4> Matched;
1290  llvm::SmallVector<ClassTemplatePartialSpecializationDecl *, 4> PartialSpecs;
1291  Template->getPartialSpecializations(PartialSpecs);
1292  for (unsigned I = 0, N = PartialSpecs.size(); I != N; ++I) {
1293    ClassTemplatePartialSpecializationDecl *Partial = PartialSpecs[I];
1294    TemplateDeductionInfo Info(Context, PointOfInstantiation);
1295    if (TemplateDeductionResult Result
1296          = DeduceTemplateArguments(Partial,
1297                                    ClassTemplateSpec->getTemplateArgs(),
1298                                    Info)) {
1299      // FIXME: Store the failed-deduction information for use in
1300      // diagnostics, later.
1301      (void)Result;
1302    } else {
1303      Matched.push_back(std::make_pair(Partial, Info.take()));
1304    }
1305  }
1306
1307  if (Matched.size() >= 1) {
1308    llvm::SmallVector<MatchResult, 4>::iterator Best = Matched.begin();
1309    if (Matched.size() == 1) {
1310      //   -- If exactly one matching specialization is found, the
1311      //      instantiation is generated from that specialization.
1312      // We don't need to do anything for this.
1313    } else {
1314      //   -- If more than one matching specialization is found, the
1315      //      partial order rules (14.5.4.2) are used to determine
1316      //      whether one of the specializations is more specialized
1317      //      than the others. If none of the specializations is more
1318      //      specialized than all of the other matching
1319      //      specializations, then the use of the class template is
1320      //      ambiguous and the program is ill-formed.
1321      for (llvm::SmallVector<MatchResult, 4>::iterator P = Best + 1,
1322                                                    PEnd = Matched.end();
1323           P != PEnd; ++P) {
1324        if (getMoreSpecializedPartialSpecialization(P->first, Best->first,
1325                                                    PointOfInstantiation)
1326              == P->first)
1327          Best = P;
1328      }
1329
1330      // Determine if the best partial specialization is more specialized than
1331      // the others.
1332      bool Ambiguous = false;
1333      for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1334                                                    PEnd = Matched.end();
1335           P != PEnd; ++P) {
1336        if (P != Best &&
1337            getMoreSpecializedPartialSpecialization(P->first, Best->first,
1338                                                    PointOfInstantiation)
1339              != Best->first) {
1340          Ambiguous = true;
1341          break;
1342        }
1343      }
1344
1345      if (Ambiguous) {
1346        // Partial ordering did not produce a clear winner. Complain.
1347        ClassTemplateSpec->setInvalidDecl();
1348        Diag(PointOfInstantiation, diag::err_partial_spec_ordering_ambiguous)
1349          << ClassTemplateSpec;
1350
1351        // Print the matching partial specializations.
1352        for (llvm::SmallVector<MatchResult, 4>::iterator P = Matched.begin(),
1353                                                      PEnd = Matched.end();
1354             P != PEnd; ++P)
1355          Diag(P->first->getLocation(), diag::note_partial_spec_match)
1356            << getTemplateArgumentBindingsText(P->first->getTemplateParameters(),
1357                                               *P->second);
1358
1359        return true;
1360      }
1361    }
1362
1363    // Instantiate using the best class template partial specialization.
1364    ClassTemplatePartialSpecializationDecl *OrigPartialSpec = Best->first;
1365    while (OrigPartialSpec->getInstantiatedFromMember()) {
1366      // If we've found an explicit specialization of this class template,
1367      // stop here and use that as the pattern.
1368      if (OrigPartialSpec->isMemberSpecialization())
1369        break;
1370
1371      OrigPartialSpec = OrigPartialSpec->getInstantiatedFromMember();
1372    }
1373
1374    Pattern = OrigPartialSpec;
1375    ClassTemplateSpec->setInstantiationOf(Best->first, Best->second);
1376  } else {
1377    //   -- If no matches are found, the instantiation is generated
1378    //      from the primary template.
1379    ClassTemplateDecl *OrigTemplate = Template;
1380    while (OrigTemplate->getInstantiatedFromMemberTemplate()) {
1381      // If we've found an explicit specialization of this class template,
1382      // stop here and use that as the pattern.
1383      if (OrigTemplate->isMemberSpecialization())
1384        break;
1385
1386      OrigTemplate = OrigTemplate->getInstantiatedFromMemberTemplate();
1387    }
1388
1389    Pattern = OrigTemplate->getTemplatedDecl();
1390  }
1391
1392  bool Result = InstantiateClass(PointOfInstantiation, ClassTemplateSpec,
1393                                 Pattern,
1394                                getTemplateInstantiationArgs(ClassTemplateSpec),
1395                                 TSK,
1396                                 Complain);
1397
1398  for (unsigned I = 0, N = Matched.size(); I != N; ++I) {
1399    // FIXME: Implement TemplateArgumentList::Destroy!
1400    //    if (Matched[I].first != Pattern)
1401    //      Matched[I].second->Destroy(Context);
1402  }
1403
1404  return Result;
1405}
1406
1407/// \brief Instantiates the definitions of all of the member
1408/// of the given class, which is an instantiation of a class template
1409/// or a member class of a template.
1410void
1411Sema::InstantiateClassMembers(SourceLocation PointOfInstantiation,
1412                              CXXRecordDecl *Instantiation,
1413                        const MultiLevelTemplateArgumentList &TemplateArgs,
1414                              TemplateSpecializationKind TSK) {
1415  for (DeclContext::decl_iterator D = Instantiation->decls_begin(),
1416                               DEnd = Instantiation->decls_end();
1417       D != DEnd; ++D) {
1418    bool SuppressNew = false;
1419    if (FunctionDecl *Function = dyn_cast<FunctionDecl>(*D)) {
1420      if (FunctionDecl *Pattern
1421            = Function->getInstantiatedFromMemberFunction()) {
1422        MemberSpecializationInfo *MSInfo
1423          = Function->getMemberSpecializationInfo();
1424        assert(MSInfo && "No member specialization information?");
1425        if (MSInfo->getTemplateSpecializationKind()
1426                                                 == TSK_ExplicitSpecialization)
1427          continue;
1428
1429        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1430                                                   Function,
1431                                        MSInfo->getTemplateSpecializationKind(),
1432                                              MSInfo->getPointOfInstantiation(),
1433                                                   SuppressNew) ||
1434            SuppressNew)
1435          continue;
1436
1437        if (Function->getBody())
1438          continue;
1439
1440        if (TSK == TSK_ExplicitInstantiationDefinition) {
1441          // C++0x [temp.explicit]p8:
1442          //   An explicit instantiation definition that names a class template
1443          //   specialization explicitly instantiates the class template
1444          //   specialization and is only an explicit instantiation definition
1445          //   of members whose definition is visible at the point of
1446          //   instantiation.
1447          if (!Pattern->getBody())
1448            continue;
1449
1450          Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1451
1452          InstantiateFunctionDefinition(PointOfInstantiation, Function);
1453        } else {
1454          Function->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1455        }
1456      }
1457    } else if (VarDecl *Var = dyn_cast<VarDecl>(*D)) {
1458      if (Var->isStaticDataMember()) {
1459        MemberSpecializationInfo *MSInfo = Var->getMemberSpecializationInfo();
1460        assert(MSInfo && "No member specialization information?");
1461        if (MSInfo->getTemplateSpecializationKind()
1462                                                 == TSK_ExplicitSpecialization)
1463          continue;
1464
1465        if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1466                                                   Var,
1467                                        MSInfo->getTemplateSpecializationKind(),
1468                                              MSInfo->getPointOfInstantiation(),
1469                                                   SuppressNew) ||
1470            SuppressNew)
1471          continue;
1472
1473        if (TSK == TSK_ExplicitInstantiationDefinition) {
1474          // C++0x [temp.explicit]p8:
1475          //   An explicit instantiation definition that names a class template
1476          //   specialization explicitly instantiates the class template
1477          //   specialization and is only an explicit instantiation definition
1478          //   of members whose definition is visible at the point of
1479          //   instantiation.
1480          if (!Var->getInstantiatedFromStaticDataMember()
1481                                                     ->getOutOfLineDefinition())
1482            continue;
1483
1484          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1485          InstantiateStaticDataMemberDefinition(PointOfInstantiation, Var);
1486        } else {
1487          Var->setTemplateSpecializationKind(TSK, PointOfInstantiation);
1488        }
1489      }
1490    } else if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(*D)) {
1491      // Always skip the injected-class-name, along with any
1492      // redeclarations of nested classes, since both would cause us
1493      // to try to instantiate the members of a class twice.
1494      if (Record->isInjectedClassName() || Record->getPreviousDeclaration())
1495        continue;
1496
1497      MemberSpecializationInfo *MSInfo = Record->getMemberSpecializationInfo();
1498      assert(MSInfo && "No member specialization information?");
1499
1500      if (MSInfo->getTemplateSpecializationKind()
1501                                                == TSK_ExplicitSpecialization)
1502        continue;
1503
1504      if (CheckSpecializationInstantiationRedecl(PointOfInstantiation, TSK,
1505                                                 Record,
1506                                        MSInfo->getTemplateSpecializationKind(),
1507                                              MSInfo->getPointOfInstantiation(),
1508                                                 SuppressNew) ||
1509          SuppressNew)
1510        continue;
1511
1512      CXXRecordDecl *Pattern = Record->getInstantiatedFromMemberClass();
1513      assert(Pattern && "Missing instantiated-from-template information");
1514
1515      if (!Record->getDefinition()) {
1516        if (!Pattern->getDefinition()) {
1517          // C++0x [temp.explicit]p8:
1518          //   An explicit instantiation definition that names a class template
1519          //   specialization explicitly instantiates the class template
1520          //   specialization and is only an explicit instantiation definition
1521          //   of members whose definition is visible at the point of
1522          //   instantiation.
1523          if (TSK == TSK_ExplicitInstantiationDeclaration) {
1524            MSInfo->setTemplateSpecializationKind(TSK);
1525            MSInfo->setPointOfInstantiation(PointOfInstantiation);
1526          }
1527
1528          continue;
1529        }
1530
1531        InstantiateClass(PointOfInstantiation, Record, Pattern,
1532                         TemplateArgs,
1533                         TSK);
1534      }
1535
1536      Pattern = cast_or_null<CXXRecordDecl>(Record->getDefinition());
1537      if (Pattern)
1538        InstantiateClassMembers(PointOfInstantiation, Pattern, TemplateArgs,
1539                                TSK);
1540    }
1541  }
1542}
1543
1544/// \brief Instantiate the definitions of all of the members of the
1545/// given class template specialization, which was named as part of an
1546/// explicit instantiation.
1547void
1548Sema::InstantiateClassTemplateSpecializationMembers(
1549                                           SourceLocation PointOfInstantiation,
1550                            ClassTemplateSpecializationDecl *ClassTemplateSpec,
1551                                               TemplateSpecializationKind TSK) {
1552  // C++0x [temp.explicit]p7:
1553  //   An explicit instantiation that names a class template
1554  //   specialization is an explicit instantion of the same kind
1555  //   (declaration or definition) of each of its members (not
1556  //   including members inherited from base classes) that has not
1557  //   been previously explicitly specialized in the translation unit
1558  //   containing the explicit instantiation, except as described
1559  //   below.
1560  InstantiateClassMembers(PointOfInstantiation, ClassTemplateSpec,
1561                          getTemplateInstantiationArgs(ClassTemplateSpec),
1562                          TSK);
1563}
1564
1565Sema::OwningStmtResult
1566Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) {
1567  if (!S)
1568    return Owned(S);
1569
1570  TemplateInstantiator Instantiator(*this, TemplateArgs,
1571                                    SourceLocation(),
1572                                    DeclarationName());
1573  return Instantiator.TransformStmt(S);
1574}
1575
1576Sema::OwningExprResult
1577Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) {
1578  if (!E)
1579    return Owned(E);
1580
1581  TemplateInstantiator Instantiator(*this, TemplateArgs,
1582                                    SourceLocation(),
1583                                    DeclarationName());
1584  return Instantiator.TransformExpr(E);
1585}
1586
1587/// \brief Do template substitution on a nested-name-specifier.
1588NestedNameSpecifier *
1589Sema::SubstNestedNameSpecifier(NestedNameSpecifier *NNS,
1590                               SourceRange Range,
1591                         const MultiLevelTemplateArgumentList &TemplateArgs) {
1592  TemplateInstantiator Instantiator(*this, TemplateArgs, Range.getBegin(),
1593                                    DeclarationName());
1594  return Instantiator.TransformNestedNameSpecifier(NNS, Range);
1595}
1596
1597TemplateName
1598Sema::SubstTemplateName(TemplateName Name, SourceLocation Loc,
1599                        const MultiLevelTemplateArgumentList &TemplateArgs) {
1600  TemplateInstantiator Instantiator(*this, TemplateArgs, Loc,
1601                                    DeclarationName());
1602  return Instantiator.TransformTemplateName(Name);
1603}
1604
1605bool Sema::Subst(const TemplateArgumentLoc &Input, TemplateArgumentLoc &Output,
1606                 const MultiLevelTemplateArgumentList &TemplateArgs) {
1607  TemplateInstantiator Instantiator(*this, TemplateArgs, SourceLocation(),
1608                                    DeclarationName());
1609
1610  return Instantiator.TransformTemplateArgument(Input, Output);
1611}
1612
1613Decl *Sema::LocalInstantiationScope::getInstantiationOf(const Decl *D) {
1614  for (LocalInstantiationScope *Current = this; Current;
1615       Current = Current->Outer) {
1616    // Check if we found something within this scope.
1617    llvm::DenseMap<const Decl *, Decl *>::iterator Found
1618      = Current->LocalDecls.find(D);
1619    if (Found != Current->LocalDecls.end())
1620      return Found->second;
1621
1622    // If we aren't combined with our outer scope, we're done.
1623    if (!Current->CombineWithOuterScope)
1624      break;
1625  }
1626
1627  assert(D->isInvalidDecl() &&
1628         "declaration was not instantiated in this scope!");
1629  return 0;
1630}
1631
1632void Sema::LocalInstantiationScope::InstantiatedLocal(const Decl *D,
1633                                                      Decl *Inst) {
1634  Decl *&Stored = LocalDecls[D];
1635  assert((!Stored || Stored == Inst)&& "Already instantiated this local");
1636  Stored = Inst;
1637}
1638