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