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