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