contrib/llvm/tools/clang/lib/Sema/SemaTemplate.cpp

   1 //===------- SemaTemplate.cpp - Semantic Analysis for C++ Templates -------===/
   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 semantic analysis for C++ templates.
  10 //===----------------------------------------------------------------------===/
  11
  12 #include "clang/Sema/SemaInternal.h"
  13 #include "clang/Sema/Lookup.h"
  14 #include "clang/Sema/Scope.h"
  15 #include "clang/Sema/Template.h"
  16 #include "clang/Sema/TemplateDeduction.h"
  17 #include "TreeTransform.h"
  18 #include "clang/AST/ASTContext.h"
  19 #include "clang/AST/Expr.h"
  20 #include "clang/AST/ExprCXX.h"
  21 #include "clang/AST/DeclFriend.h"
  22 #include "clang/AST/DeclTemplate.h"
  23 #include "clang/AST/RecursiveASTVisitor.h"
  24 #include "clang/AST/TypeVisitor.h"
  25 #include "clang/Sema/DeclSpec.h"
  26 #include "clang/Sema/ParsedTemplate.h"
  27 #include "clang/Basic/LangOptions.h"
  28 #include "clang/Basic/PartialDiagnostic.h"
  29 #include "llvm/ADT/StringExtras.h"
  30 using namespace clang;
  31 using namespace sema;
  32
  33 // Exported for use by Parser.
  34 SourceRange
  35 clang::getTemplateParamsRange(TemplateParameterList const * const *Ps,
  36                               unsigned N) {
  37   if (!N) return SourceRange();
  38   return SourceRange(Ps[0]->getTemplateLoc(), Ps[N-1]->getRAngleLoc());
  39 }
  40
  41 /// \brief Determine whether the declaration found is acceptable as the name
  42 /// of a template and, if so, return that template declaration. Otherwise,
  43 /// returns NULL.
  44 static NamedDecl *isAcceptableTemplateName(ASTContext &Context,
  45                                            NamedDecl *Orig) {
  46   NamedDecl *D = Orig->getUnderlyingDecl();
  47
  48   if (isa<TemplateDecl>(D))
  49     return Orig;
  50
  51   if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D)) {
  52     // C++ [temp.local]p1:
  53     //   Like normal (non-template) classes, class templates have an
  54     //   injected-class-name (Clause 9). The injected-class-name
  55     //   can be used with or without a template-argument-list. When
  56     //   it is used without a template-argument-list, it is
  57     //   equivalent to the injected-class-name followed by the
  58     //   template-parameters of the class template enclosed in
  59     //   <>. When it is used with a template-argument-list, it
  60     //   refers to the specified class template specialization,
  61     //   which could be the current specialization or another
  62     //   specialization.
  63     if (Record->isInjectedClassName()) {
  64       Record = cast<CXXRecordDecl>(Record->getDeclContext());
  65       if (Record->getDescribedClassTemplate())
  66         return Record->getDescribedClassTemplate();
  67
  68       if (ClassTemplateSpecializationDecl *Spec
  69             = dyn_cast<ClassTemplateSpecializationDecl>(Record))
  70         return Spec->getSpecializedTemplate();
  71     }
  72
  73     return 0;
  74   }
  75
  76   return 0;
  77 }
  78
  79 static void FilterAcceptableTemplateNames(ASTContext &C, LookupResult &R) {
  80   // The set of class templates we've already seen.
  81   llvm::SmallPtrSet<ClassTemplateDecl *, 8> ClassTemplates;
  82   LookupResult::Filter filter = R.makeFilter();
  83   while (filter.hasNext()) {
  84     NamedDecl *Orig = filter.next();
  85     NamedDecl *Repl = isAcceptableTemplateName(C, Orig);
  86     if (!Repl)
  87       filter.erase();
  88     else if (Repl != Orig) {
  89
  90       // C++ [temp.local]p3:
  91       //   A lookup that finds an injected-class-name (10.2) can result in an
  92       //   ambiguity in certain cases (for example, if it is found in more than
  93       //   one base class). If all of the injected-class-names that are found
  94       //   refer to specializations of the same class template, and if the name
  95       //   is followed by a template-argument-list, the reference refers to the
  96       //   class template itself and not a specialization thereof, and is not
  97       //   ambiguous.
  98       //
  99       // FIXME: Will we eventually have to do the same for alias templates?
 100       if (ClassTemplateDecl *ClassTmpl = dyn_cast<ClassTemplateDecl>(Repl))
 101         if (!ClassTemplates.insert(ClassTmpl)) {
 102           filter.erase();
 103           continue;
 104         }
 105
 106       // FIXME: we promote access to public here as a workaround to
 107       // the fact that LookupResult doesn't let us remember that we
 108       // found this template through a particular injected class name,
 109       // which means we end up doing nasty things to the invariants.
 110       // Pretending that access is public is *much* safer.
 111       filter.replace(Repl, AS_public);
 112     }
 113   }
 114   filter.done();
 115 }
 116
 117 TemplateNameKind Sema::isTemplateName(Scope *S,
 118                                       CXXScopeSpec &SS,
 119                                       bool hasTemplateKeyword,
 120                                       UnqualifiedId &Name,
 121                                       ParsedType ObjectTypePtr,
 122                                       bool EnteringContext,
 123                                       TemplateTy &TemplateResult,
 124                                       bool &MemberOfUnknownSpecialization) {
 125   assert(getLangOptions().CPlusPlus && "No template names in C!");
 126
 127   DeclarationName TName;
 128   MemberOfUnknownSpecialization = false;
 129
 130   switch (Name.getKind()) {
 131   case UnqualifiedId::IK_Identifier:
 132     TName = DeclarationName(Name.Identifier);
 133     break;
 134
 135   case UnqualifiedId::IK_OperatorFunctionId:
 136     TName = Context.DeclarationNames.getCXXOperatorName(
 137                                               Name.OperatorFunctionId.Operator);
 138     break;
 139
 140   case UnqualifiedId::IK_LiteralOperatorId:
 141     TName = Context.DeclarationNames.getCXXLiteralOperatorName(Name.Identifier);
 142     break;
 143
 144   default:
 145     return TNK_Non_template;
 146   }
 147
 148   QualType ObjectType = ObjectTypePtr.get();
 149
 150   LookupResult R(*this, TName, Name.getSourceRange().getBegin(),
 151                  LookupOrdinaryName);
 152   LookupTemplateName(R, S, SS, ObjectType, EnteringContext,
 153                      MemberOfUnknownSpecialization);
 154   if (R.empty()) return TNK_Non_template;
 155   if (R.isAmbiguous()) {
 156     // Suppress diagnostics;  we'll redo this lookup later.
 157     R.suppressDiagnostics();
 158
 159     // FIXME: we might have ambiguous templates, in which case we
 160     // should at least parse them properly!
 161     return TNK_Non_template;
 162   }
 163
 164   TemplateName Template;
 165   TemplateNameKind TemplateKind;
 166
 167   unsigned ResultCount = R.end() - R.begin();
 168   if (ResultCount > 1) {
 169     // We assume that we'll preserve the qualifier from a function
 170     // template name in other ways.
 171     Template = Context.getOverloadedTemplateName(R.begin(), R.end());
 172     TemplateKind = TNK_Function_template;
 173
 174     // We'll do this lookup again later.
 175     R.suppressDiagnostics();
 176   } else {
 177     TemplateDecl *TD = cast<TemplateDecl>((*R.begin())->getUnderlyingDecl());
 178
 179     if (SS.isSet() && !SS.isInvalid()) {
 180       NestedNameSpecifier *Qualifier
 181         = static_cast<NestedNameSpecifier *>(SS.getScopeRep());
 182       Template = Context.getQualifiedTemplateName(Qualifier,
 183                                                   hasTemplateKeyword, TD);
 184     } else {
 185       Template = TemplateName(TD);
 186     }
 187
 188     if (isa<FunctionTemplateDecl>(TD)) {
 189       TemplateKind = TNK_Function_template;
 190
 191       // We'll do this lookup again later.
 192       R.suppressDiagnostics();
 193     } else {
 194       assert(isa<ClassTemplateDecl>(TD) || isa<TemplateTemplateParmDecl>(TD));
 195       TemplateKind = TNK_Type_template;
 196     }
 197   }
 198
 199   TemplateResult = TemplateTy::make(Template);
 200   return TemplateKind;
 201 }
 202
 203 bool Sema::DiagnoseUnknownTemplateName(const IdentifierInfo &II,
 204                                        SourceLocation IILoc,
 205                                        Scope *S,
 206                                        const CXXScopeSpec *SS,
 207                                        TemplateTy &SuggestedTemplate,
 208                                        TemplateNameKind &SuggestedKind) {
 209   // We can't recover unless there's a dependent scope specifier preceding the
 210   // template name.
 211   // FIXME: Typo correction?
 212   if (!SS || !SS->isSet() || !isDependentScopeSpecifier(*SS) ||
 213       computeDeclContext(*SS))
 214     return false;
 215
 216   // The code is missing a 'template' keyword prior to the dependent template
 217   // name.
 218   NestedNameSpecifier *Qualifier = (NestedNameSpecifier*)SS->getScopeRep();
 219   Diag(IILoc, diag::err_template_kw_missing)
 220     << Qualifier << II.getName()
 221     << FixItHint::CreateInsertion(IILoc, "template ");
 222   SuggestedTemplate
 223     = TemplateTy::make(Context.getDependentTemplateName(Qualifier, &II));
 224   SuggestedKind = TNK_Dependent_template_name;
 225   return true;
 226 }
 227
 228 void Sema::LookupTemplateName(LookupResult &Found,
 229                               Scope *S, CXXScopeSpec &SS,
 230                               QualType ObjectType,
 231                               bool EnteringContext,
 232                               bool &MemberOfUnknownSpecialization) {
 233   // Determine where to perform name lookup
 234   MemberOfUnknownSpecialization = false;
 235   DeclContext *LookupCtx = 0;
 236   bool isDependent = false;
 237   if (!ObjectType.isNull()) {
 238     // This nested-name-specifier occurs in a member access expression, e.g.,
 239     // x->B::f, and we are looking into the type of the object.
 240     assert(!SS.isSet() && "ObjectType and scope specifier cannot coexist");
 241     LookupCtx = computeDeclContext(ObjectType);
 242     isDependent = ObjectType->isDependentType();
 243     assert((isDependent || !ObjectType->isIncompleteType()) &&
 244            "Caller should have completed object type");
 245   } else if (SS.isSet()) {
 246     // This nested-name-specifier occurs after another nested-name-specifier,
 247     // so long into the context associated with the prior nested-name-specifier.
 248     LookupCtx = computeDeclContext(SS, EnteringContext);
 249     isDependent = isDependentScopeSpecifier(SS);
 250
 251     // The declaration context must be complete.
 252     if (LookupCtx && RequireCompleteDeclContext(SS, LookupCtx))
 253       return;
 254   }
 255
 256   bool ObjectTypeSearchedInScope = false;
 257   if (LookupCtx) {
 258     // Perform "qualified" name lookup into the declaration context we
 259     // computed, which is either the type of the base of a member access
 260     // expression or the declaration context associated with a prior
 261     // nested-name-specifier.
 262     LookupQualifiedName(Found, LookupCtx);
 263
 264     if (!ObjectType.isNull() && Found.empty()) {
 265       // C++ [basic.lookup.classref]p1:
 266       //   In a class member access expression (5.2.5), if the . or -> token is
 267       //   immediately followed by an identifier followed by a <, the
 268       //   identifier must be looked up to determine whether the < is the
 269       //   beginning of a template argument list (14.2) or a less-than operator.
 270       //   The identifier is first looked up in the class of the object
 271       //   expression. If the identifier is not found, it is then looked up in
 272       //   the context of the entire postfix-expression and shall name a class
 273       //   or function template.
 274       if (S) LookupName(Found, S);
 275       ObjectTypeSearchedInScope = true;
 276     }
 277   } else if (isDependent && (!S || ObjectType.isNull())) {
 278     // We cannot look into a dependent object type or nested nme
 279     // specifier.
 280     MemberOfUnknownSpecialization = true;
 281     return;
 282   } else {
 283     // Perform unqualified name lookup in the current scope.
 284     LookupName(Found, S);
 285   }
 286
 287   if (Found.empty() && !isDependent) {
 288     // If we did not find any names, attempt to correct any typos.
 289     DeclarationName Name = Found.getLookupName();
 290     if (DeclarationName Corrected = CorrectTypo(Found, S, &SS, LookupCtx,
 291                                                 false, CTC_CXXCasts)) {
 292       FilterAcceptableTemplateNames(Context, Found);
 293       if (!Found.empty()) {
 294         if (LookupCtx)
 295           Diag(Found.getNameLoc(), diag::err_no_member_template_suggest)
 296             << Name << LookupCtx << Found.getLookupName() << SS.getRange()
 297             << FixItHint::CreateReplacement(Found.getNameLoc(),
 298                                           Found.getLookupName().getAsString());
 299         else
 300           Diag(Found.getNameLoc(), diag::err_no_template_suggest)
 301             << Name << Found.getLookupName()
 302             << FixItHint::CreateReplacement(Found.getNameLoc(),
 303                                           Found.getLookupName().getAsString());
 304         if (TemplateDecl *Template = Found.getAsSingle<TemplateDecl>())
 305           Diag(Template->getLocation(), diag::note_previous_decl)
 306             << Template->getDeclName();
 307       }
 308     } else {
 309       Found.clear();
 310       Found.setLookupName(Name);
 311     }
 312   }
 313
 314   FilterAcceptableTemplateNames(Context, Found);
 315   if (Found.empty()) {
 316     if (isDependent)
 317       MemberOfUnknownSpecialization = true;
 318     return;
 319   }
 320
 321   if (S && !ObjectType.isNull() && !ObjectTypeSearchedInScope) {
 322     // C++ [basic.lookup.classref]p1:
 323     //   [...] If the lookup in the class of the object expression finds a
 324     //   template, the name is also looked up in the context of the entire
 325     //   postfix-expression and [...]
 326     //
 327     LookupResult FoundOuter(*this, Found.getLookupName(), Found.getNameLoc(),
 328                             LookupOrdinaryName);
 329     LookupName(FoundOuter, S);
 330     FilterAcceptableTemplateNames(Context, FoundOuter);
 331
 332     if (FoundOuter.empty()) {
 333       //   - if the name is not found, the name found in the class of the
 334       //     object expression is used, otherwise
 335     } else if (!FoundOuter.getAsSingle<ClassTemplateDecl>()) {
 336       //   - if the name is found in the context of the entire
 337       //     postfix-expression and does not name a class template, the name
 338       //     found in the class of the object expression is used, otherwise
 339     } else if (!Found.isSuppressingDiagnostics()) {
 340       //   - if the name found is a class template, it must refer to the same
 341       //     entity as the one found in the class of the object expression,
 342       //     otherwise the program is ill-formed.
 343       if (!Found.isSingleResult() ||
 344           Found.getFoundDecl()->getCanonicalDecl()
 345             != FoundOuter.getFoundDecl()->getCanonicalDecl()) {
 346         Diag(Found.getNameLoc(),
 347              diag::ext_nested_name_member_ref_lookup_ambiguous)
 348           << Found.getLookupName()
 349           << ObjectType;
 350         Diag(Found.getRepresentativeDecl()->getLocation(),
 351              diag::note_ambig_member_ref_object_type)
 352           << ObjectType;
 353         Diag(FoundOuter.getFoundDecl()->getLocation(),
 354              diag::note_ambig_member_ref_scope);
 355
 356         // Recover by taking the template that we found in the object
 357         // expression's type.
 358       }
 359     }
 360   }
 361 }
 362
 363 /// ActOnDependentIdExpression - Handle a dependent id-expression that
 364 /// was just parsed.  This is only possible with an explicit scope
 365 /// specifier naming a dependent type.
 366 ExprResult
 367 Sema::ActOnDependentIdExpression(const CXXScopeSpec &SS,
 368                                  const DeclarationNameInfo &NameInfo,
 369                                  bool isAddressOfOperand,
 370                            const TemplateArgumentListInfo *TemplateArgs) {
 371   NestedNameSpecifier *Qualifier
 372     = static_cast<NestedNameSpecifier*>(SS.getScopeRep());
 373
 374   DeclContext *DC = getFunctionLevelDeclContext();
 375
 376   if (!isAddressOfOperand &&
 377       isa<CXXMethodDecl>(DC) &&
 378       cast<CXXMethodDecl>(DC)->isInstance()) {
 379     QualType ThisType = cast<CXXMethodDecl>(DC)->getThisType(Context);
 380
 381     // Since the 'this' expression is synthesized, we don't need to
 382     // perform the double-lookup check.
 383     NamedDecl *FirstQualifierInScope = 0;
 384
 385     return Owned(CXXDependentScopeMemberExpr::Create(Context,
 386                                                      /*This*/ 0, ThisType,
 387                                                      /*IsArrow*/ true,
 388                                                      /*Op*/ SourceLocation(),
 389                                                      Qualifier, SS.getRange(),
 390                                                      FirstQualifierInScope,
 391                                                      NameInfo,
 392                                                      TemplateArgs));
 393   }
 394
 395   return BuildDependentDeclRefExpr(SS, NameInfo, TemplateArgs);
 396 }
 397
 398 ExprResult
 399 Sema::BuildDependentDeclRefExpr(const CXXScopeSpec &SS,
 400                                 const DeclarationNameInfo &NameInfo,
 401                                 const TemplateArgumentListInfo *TemplateArgs) {
 402   return Owned(DependentScopeDeclRefExpr::Create(Context,
 403                static_cast<NestedNameSpecifier*>(SS.getScopeRep()),
 404                                                  SS.getRange(),
 405                                                  NameInfo,
 406                                                  TemplateArgs));
 407 }
 408
 409 /// DiagnoseTemplateParameterShadow - Produce a diagnostic complaining
 410 /// that the template parameter 'PrevDecl' is being shadowed by a new
 411 /// declaration at location Loc. Returns true to indicate that this is
 412 /// an error, and false otherwise.
 413 bool Sema::DiagnoseTemplateParameterShadow(SourceLocation Loc, Decl *PrevDecl) {
 414   assert(PrevDecl->isTemplateParameter() && "Not a template parameter");
 415
 416   // Microsoft Visual C++ permits template parameters to be shadowed.
 417   if (getLangOptions().Microsoft)
 418     return false;
 419
 420   // C++ [temp.local]p4:
 421   //   A template-parameter shall not be redeclared within its
 422   //   scope (including nested scopes).
 423   Diag(Loc, diag::err_template_param_shadow)
 424     << cast<NamedDecl>(PrevDecl)->getDeclName();
 425   Diag(PrevDecl->getLocation(), diag::note_template_param_here);
 426   return true;
 427 }
 428
 429 /// AdjustDeclIfTemplate - If the given decl happens to be a template, reset
 430 /// the parameter D to reference the templated declaration and return a pointer
 431 /// to the template declaration. Otherwise, do nothing to D and return null.
 432 TemplateDecl *Sema::AdjustDeclIfTemplate(Decl *&D) {
 433   if (TemplateDecl *Temp = dyn_cast_or_null<TemplateDecl>(D)) {
 434     D = Temp->getTemplatedDecl();
 435     return Temp;
 436   }
 437   return 0;
 438 }
 439
 440 ParsedTemplateArgument ParsedTemplateArgument::getTemplatePackExpansion(
 441                                              SourceLocation EllipsisLoc) const {
 442   assert(Kind == Template &&
 443          "Only template template arguments can be pack expansions here");
 444   assert(getAsTemplate().get().containsUnexpandedParameterPack() &&
 445          "Template template argument pack expansion without packs");
 446   ParsedTemplateArgument Result(*this);
 447   Result.EllipsisLoc = EllipsisLoc;
 448   return Result;
 449 }
 450
 451 static TemplateArgumentLoc translateTemplateArgument(Sema &SemaRef,
 452                                             const ParsedTemplateArgument &Arg) {
 453
 454   switch (Arg.getKind()) {
 455   case ParsedTemplateArgument::Type: {
 456     TypeSourceInfo *DI;
 457     QualType T = SemaRef.GetTypeFromParser(Arg.getAsType(), &DI);
 458     if (!DI)
 459       DI = SemaRef.Context.getTrivialTypeSourceInfo(T, Arg.getLocation());
 460     return TemplateArgumentLoc(TemplateArgument(T), DI);
 461   }
 462
 463   case ParsedTemplateArgument::NonType: {
 464     Expr *E = static_cast<Expr *>(Arg.getAsExpr());
 465     return TemplateArgumentLoc(TemplateArgument(E), E);
 466   }
 467
 468   case ParsedTemplateArgument::Template: {
 469     TemplateName Template = Arg.getAsTemplate().get();
 470     TemplateArgument TArg;
 471     if (Arg.getEllipsisLoc().isValid())
 472       TArg = TemplateArgument(Template, llvm::Optional<unsigned int>());
 473     else
 474       TArg = Template;
 475     return TemplateArgumentLoc(TArg,
 476                                Arg.getScopeSpec().getRange(),
 477                                Arg.getLocation(),
 478                                Arg.getEllipsisLoc());
 479   }
 480   }
 481
 482   llvm_unreachable("Unhandled parsed template argument");
 483   return TemplateArgumentLoc();
 484 }
 485
 486 /// \brief Translates template arguments as provided by the parser
 487 /// into template arguments used by semantic analysis.
 488 void Sema::translateTemplateArguments(const ASTTemplateArgsPtr &TemplateArgsIn,
 489                                       TemplateArgumentListInfo &TemplateArgs) {
 490  for (unsigned I = 0, Last = TemplateArgsIn.size(); I != Last; ++I)
 491    TemplateArgs.addArgument(translateTemplateArgument(*this,
 492                                                       TemplateArgsIn[I]));
 493 }
 494
 495 /// ActOnTypeParameter - Called when a C++ template type parameter
 496 /// (e.g., "typename T") has been parsed. Typename specifies whether
 497 /// the keyword "typename" was used to declare the type parameter
 498 /// (otherwise, "class" was used), and KeyLoc is the location of the
 499 /// "class" or "typename" keyword. ParamName is the name of the
 500 /// parameter (NULL indicates an unnamed template parameter) and
 501 /// ParamName is the location of the parameter name (if any).
 502 /// If the type parameter has a default argument, it will be added
 503 /// later via ActOnTypeParameterDefault.
 504 Decl *Sema::ActOnTypeParameter(Scope *S, bool Typename, bool Ellipsis,
 505                                SourceLocation EllipsisLoc,
 506                                SourceLocation KeyLoc,
 507                                IdentifierInfo *ParamName,
 508                                SourceLocation ParamNameLoc,
 509                                unsigned Depth, unsigned Position,
 510                                SourceLocation EqualLoc,
 511                                ParsedType DefaultArg) {
 512   assert(S->isTemplateParamScope() &&
 513          "Template type parameter not in template parameter scope!");
 514   bool Invalid = false;
 515
 516   if (ParamName) {
 517     NamedDecl *PrevDecl = LookupSingleName(S, ParamName, ParamNameLoc,
 518                                            LookupOrdinaryName,
 519                                            ForRedeclaration);
 520     if (PrevDecl && PrevDecl->isTemplateParameter())
 521       Invalid = Invalid || DiagnoseTemplateParameterShadow(ParamNameLoc,
 522                                                            PrevDecl);
 523   }
 524
 525   SourceLocation Loc = ParamNameLoc;
 526   if (!ParamName)
 527     Loc = KeyLoc;
 528
 529   TemplateTypeParmDecl *Param
 530     = TemplateTypeParmDecl::Create(Context, Context.getTranslationUnitDecl(),
 531                                    Loc, Depth, Position, ParamName, Typename,
 532                                    Ellipsis);
 533   if (Invalid)
 534     Param->setInvalidDecl();
 535
 536   if (ParamName) {
 537     // Add the template parameter into the current scope.
 538     S->AddDecl(Param);
 539     IdResolver.AddDecl(Param);
 540   }
 541
 542   // C++0x [temp.param]p9:
 543   //   A default template-argument may be specified for any kind of
 544   //   template-parameter that is not a template parameter pack.
 545   if (DefaultArg && Ellipsis) {
 546     Diag(EqualLoc, diag::err_template_param_pack_default_arg);
 547     DefaultArg = ParsedType();
 548   }
 549
 550   // Handle the default argument, if provided.
 551   if (DefaultArg) {
 552     TypeSourceInfo *DefaultTInfo;
 553     GetTypeFromParser(DefaultArg, &DefaultTInfo);
 554
 555     assert(DefaultTInfo && "expected source information for type");
 556
 557     // Check for unexpanded parameter packs.
 558     if (DiagnoseUnexpandedParameterPack(Loc, DefaultTInfo,
 559                                         UPPC_DefaultArgument))
 560       return Param;
 561
 562     // Check the template argument itself.
 563     if (CheckTemplateArgument(Param, DefaultTInfo)) {
 564       Param->setInvalidDecl();
 565       return Param;
 566     }
 567
 568     Param->setDefaultArgument(DefaultTInfo, false);
 569   }
 570
 571   return Param;
 572 }
 573
 574 /// \brief Check that the type of a non-type template parameter is
 575 /// well-formed.
 576 ///
 577 /// \returns the (possibly-promoted) parameter type if valid;
 578 /// otherwise, produces a diagnostic and returns a NULL type.
 579 QualType
 580 Sema::CheckNonTypeTemplateParameterType(QualType T, SourceLocation Loc) {
 581   // We don't allow variably-modified types as the type of non-type template
 582   // parameters.
 583   if (T->isVariablyModifiedType()) {
 584     Diag(Loc, diag::err_variably_modified_nontype_template_param)
 585       << T;
 586     return QualType();
 587   }
 588
 589   // C++ [temp.param]p4:
 590   //
 591   // A non-type template-parameter shall have one of the following
 592   // (optionally cv-qualified) types:
 593   //
 594   //       -- integral or enumeration type,
 595   if (T->isIntegralOrEnumerationType() ||
 596       //   -- pointer to object or pointer to function,
 597       T->isPointerType() ||
 598       //   -- reference to object or reference to function,
 599       T->isReferenceType() ||
 600       //   -- pointer to member.
 601       T->isMemberPointerType() ||
 602       // If T is a dependent type, we can't do the check now, so we
 603       // assume that it is well-formed.
 604       T->isDependentType())
 605     return T;
 606   // C++ [temp.param]p8:
 607   //
 608   //   A non-type template-parameter of type "array of T" or
 609   //   "function returning T" is adjusted to be of type "pointer to
 610   //   T" or "pointer to function returning T", respectively.
 611   else if (T->isArrayType())
 612     // FIXME: Keep the type prior to promotion?
 613     return Context.getArrayDecayedType(T);
 614   else if (T->isFunctionType())
 615     // FIXME: Keep the type prior to promotion?
 616     return Context.getPointerType(T);
 617
 618   Diag(Loc, diag::err_template_nontype_parm_bad_type)
 619     << T;
 620
 621   return QualType();
 622 }
 623
 624 Decl *Sema::ActOnNonTypeTemplateParameter(Scope *S, Declarator &D,
 625                                           unsigned Depth,
 626                                           unsigned Position,
 627                                           SourceLocation EqualLoc,
 628                                           Expr *Default) {
 629   TypeSourceInfo *TInfo = GetTypeForDeclarator(D, S);
 630   QualType T = TInfo->getType();
 631
 632   assert(S->isTemplateParamScope() &&
 633          "Non-type template parameter not in template parameter scope!");
 634   bool Invalid = false;
 635
 636   IdentifierInfo *ParamName = D.getIdentifier();
 637   if (ParamName) {
 638     NamedDecl *PrevDecl = LookupSingleName(S, ParamName, D.getIdentifierLoc(),
 639                                            LookupOrdinaryName,
 640                                            ForRedeclaration);
 641     if (PrevDecl && PrevDecl->isTemplateParameter())
 642       Invalid = Invalid || DiagnoseTemplateParameterShadow(D.getIdentifierLoc(),
 643                                                            PrevDecl);
 644   }
 645
 646   T = CheckNonTypeTemplateParameterType(T, D.getIdentifierLoc());
 647   if (T.isNull()) {
 648     T = Context.IntTy; // Recover with an 'int' type.
 649     Invalid = true;
 650   }
 651
 652   bool IsParameterPack = D.hasEllipsis();
 653   NonTypeTemplateParmDecl *Param
 654     = NonTypeTemplateParmDecl::Create(Context, Context.getTranslationUnitDecl(),
 655                                       D.getIdentifierLoc(),
 656                                       Depth, Position, ParamName, T,
 657                                       IsParameterPack, TInfo);
 658   if (Invalid)
 659     Param->setInvalidDecl();
 660
 661   if (D.getIdentifier()) {
 662     // Add the template parameter into the current scope.
 663     S->AddDecl(Param);
 664     IdResolver.AddDecl(Param);
 665   }
 666
 667   // C++0x [temp.param]p9:
 668   //   A default template-argument may be specified for any kind of
 669   //   template-parameter that is not a template parameter pack.
 670   if (Default && IsParameterPack) {
 671     Diag(EqualLoc, diag::err_template_param_pack_default_arg);
 672     Default = 0;
 673   }
 674
 675   // Check the well-formedness of the default template argument, if provided.
 676   if (Default) {
 677     // Check for unexpanded parameter packs.
 678     if (DiagnoseUnexpandedParameterPack(Default, UPPC_DefaultArgument))
 679       return Param;
 680
 681     TemplateArgument Converted;
 682     if (CheckTemplateArgument(Param, Param->getType(), Default, Converted)) {
 683       Param->setInvalidDecl();
 684       return Param;
 685     }
 686
 687     Param->setDefaultArgument(Default, false);
 688   }
 689
 690   return Param;
 691 }
 692
 693 /// ActOnTemplateTemplateParameter - Called when a C++ template template
 694 /// parameter (e.g. T in template <template <typename> class T> class array)
 695 /// has been parsed. S is the current scope.
 696 Decl *Sema::ActOnTemplateTemplateParameter(Scope* S,
 697                                            SourceLocation TmpLoc,
 698                                            TemplateParamsTy *Params,
 699                                            SourceLocation EllipsisLoc,
 700                                            IdentifierInfo *Name,
 701                                            SourceLocation NameLoc,
 702                                            unsigned Depth,
 703                                            unsigned Position,
 704                                            SourceLocation EqualLoc,
 705                                            ParsedTemplateArgument Default) {
 706   assert(S->isTemplateParamScope() &&
 707          "Template template parameter not in template parameter scope!");
 708
 709   // Construct the parameter object.
 710   bool IsParameterPack = EllipsisLoc.isValid();
 711   // FIXME: Pack-ness is dropped
 712   TemplateTemplateParmDecl *Param =
 713     TemplateTemplateParmDecl::Create(Context, Context.getTranslationUnitDecl(),
 714                                      NameLoc.isInvalid()? TmpLoc : NameLoc,
 715                                      Depth, Position, IsParameterPack,
 716                                      Name, Params);
 717
 718   // If the template template parameter has a name, then link the identifier
 719   // into the scope and lookup mechanisms.
 720   if (Name) {
 721     S->AddDecl(Param);
 722     IdResolver.AddDecl(Param);
 723   }
 724
 725   if (Params->size() == 0) {
 726     Diag(Param->getLocation(), diag::err_template_template_parm_no_parms)
 727     << SourceRange(Params->getLAngleLoc(), Params->getRAngleLoc());
 728     Param->setInvalidDecl();
 729   }
 730
 731   // C++0x [temp.param]p9:
 732   //   A default template-argument may be specified for any kind of
 733   //   template-parameter that is not a template parameter pack.
 734   if (IsParameterPack && !Default.isInvalid()) {
 735     Diag(EqualLoc, diag::err_template_param_pack_default_arg);
 736     Default = ParsedTemplateArgument();
 737   }
 738
 739   if (!Default.isInvalid()) {
 740     // Check only that we have a template template argument. We don't want to
 741     // try to check well-formedness now, because our template template parameter
 742     // might have dependent types in its template parameters, which we wouldn't
 743     // be able to match now.
 744     //
 745     // If none of the template template parameter's template arguments mention
 746     // other template parameters, we could actually perform more checking here.
 747     // However, it isn't worth doing.
 748     TemplateArgumentLoc DefaultArg = translateTemplateArgument(*this, Default);
 749     if (DefaultArg.getArgument().getAsTemplate().isNull()) {
 750       Diag(DefaultArg.getLocation(), diag::err_template_arg_not_class_template)
 751         << DefaultArg.getSourceRange();
 752       return Param;
 753     }
 754
 755     // Check for unexpanded parameter packs.
 756     if (DiagnoseUnexpandedParameterPack(DefaultArg.getLocation(),
 757                                         DefaultArg.getArgument().getAsTemplate(),
 758                                         UPPC_DefaultArgument))
 759       return Param;
 760
 761     Param->setDefaultArgument(DefaultArg, false);
 762   }
 763
 764   return Param;
 765 }
 766
 767 /// ActOnTemplateParameterList - Builds a TemplateParameterList that
 768 /// contains the template parameters in Params/NumParams.
 769 Sema::TemplateParamsTy *
 770 Sema::ActOnTemplateParameterList(unsigned Depth,
 771                                  SourceLocation ExportLoc,
 772                                  SourceLocation TemplateLoc,
 773                                  SourceLocation LAngleLoc,
 774                                  Decl **Params, unsigned NumParams,
 775                                  SourceLocation RAngleLoc) {
 776   if (ExportLoc.isValid())
 777     Diag(ExportLoc, diag::warn_template_export_unsupported);
 778
 779   return TemplateParameterList::Create(Context, TemplateLoc, LAngleLoc,
 780                                        (NamedDecl**)Params, NumParams,
 781                                        RAngleLoc);
 782 }
 783
 784 static void SetNestedNameSpecifier(TagDecl *T, const CXXScopeSpec &SS) {
 785   if (SS.isSet())
 786     T->setQualifierInfo(static_cast<NestedNameSpecifier*>(SS.getScopeRep()),
 787                         SS.getRange());
 788 }
 789
 790 DeclResult
 791 Sema::CheckClassTemplate(Scope *S, unsigned TagSpec, TagUseKind TUK,
 792                          SourceLocation KWLoc, CXXScopeSpec &SS,
 793                          IdentifierInfo *Name, SourceLocation NameLoc,
 794                          AttributeList *Attr,
 795                          TemplateParameterList *TemplateParams,
 796                          AccessSpecifier AS) {
 797   assert(TemplateParams && TemplateParams->size() > 0 &&
 798          "No template parameters");
 799   assert(TUK != TUK_Reference && "Can only declare or define class templates");
 800   bool Invalid = false;
 801
 802   // Check that we can declare a template here.
 803   if (CheckTemplateDeclScope(S, TemplateParams))
 804     return true;
 805
 806   TagTypeKind Kind = TypeWithKeyword::getTagTypeKindForTypeSpec(TagSpec);
 807   assert(Kind != TTK_Enum && "can't build template of enumerated type");
 808
 809   // There is no such thing as an unnamed class template.
 810   if (!Name) {
 811     Diag(KWLoc, diag::err_template_unnamed_class);
 812     return true;
 813   }
 814
 815   // Find any previous declaration with this name.
 816   DeclContext *SemanticContext;
 817   LookupResult Previous(*this, Name, NameLoc, LookupOrdinaryName,
 818                         ForRedeclaration);
 819   if (SS.isNotEmpty() && !SS.isInvalid()) {
 820     SemanticContext = computeDeclContext(SS, true);
 821     if (!SemanticContext) {
 822       // FIXME: Produce a reasonable diagnostic here
 823       return true;
 824     }
 825
 826     if (RequireCompleteDeclContext(SS, SemanticContext))
 827       return true;
 828
 829     LookupQualifiedName(Previous, SemanticContext);
 830   } else {
 831     SemanticContext = CurContext;
 832     LookupName(Previous, S);
 833   }
 834
 835   if (Previous.isAmbiguous())
 836     return true;
 837
 838   NamedDecl *PrevDecl = 0;
 839   if (Previous.begin() != Previous.end())
 840     PrevDecl = (*Previous.begin())->getUnderlyingDecl();
 841
 842   // If there is a previous declaration with the same name, check
 843   // whether this is a valid redeclaration.
 844   ClassTemplateDecl *PrevClassTemplate
 845     = dyn_cast_or_null<ClassTemplateDecl>(PrevDecl);
 846
 847   // We may have found the injected-class-name of a class template,
 848   // class template partial specialization, or class template specialization.
 849   // In these cases, grab the template that is being defined or specialized.
 850   if (!PrevClassTemplate && PrevDecl && isa<CXXRecordDecl>(PrevDecl) &&
 851       cast<CXXRecordDecl>(PrevDecl)->isInjectedClassName()) {
 852     PrevDecl = cast<CXXRecordDecl>(PrevDecl->getDeclContext());
 853     PrevClassTemplate
 854       = cast<CXXRecordDecl>(PrevDecl)->getDescribedClassTemplate();
 855     if (!PrevClassTemplate && isa<ClassTemplateSpecializationDecl>(PrevDecl)) {
 856       PrevClassTemplate
 857         = cast<ClassTemplateSpecializationDecl>(PrevDecl)
 858             ->getSpecializedTemplate();
 859     }
 860   }
 861
 862   if (TUK == TUK_Friend) {
 863     // C++ [namespace.memdef]p3:
 864     //   [...] When looking for a prior declaration of a class or a function
 865     //   declared as a friend, and when the name of the friend class or
 866     //   function is neither a qualified name nor a template-id, scopes outside
 867     //   the innermost enclosing namespace scope are not considered.
 868     if (!SS.isSet()) {
 869       DeclContext *OutermostContext = CurContext;
 870       while (!OutermostContext->isFileContext())
 871         OutermostContext = OutermostContext->getLookupParent();
 872
 873       if (PrevDecl &&
 874           (OutermostContext->Equals(PrevDecl->getDeclContext()) ||
 875            OutermostContext->Encloses(PrevDecl->getDeclContext()))) {
 876         SemanticContext = PrevDecl->getDeclContext();
 877       } else {
 878         // Declarations in outer scopes don't matter. However, the outermost
 879         // context we computed is the semantic context for our new
 880         // declaration.
 881         PrevDecl = PrevClassTemplate = 0;
 882         SemanticContext = OutermostContext;
 883       }
 884     }
 885
 886     if (CurContext->isDependentContext()) {
 887       // If this is a dependent context, we don't want to link the friend
 888       // class template to the template in scope, because that would perform
 889       // checking of the template parameter lists that can't be performed
 890       // until the outer context is instantiated.
 891       PrevDecl = PrevClassTemplate = 0;
 892     }
 893   } else if (PrevDecl && !isDeclInScope(PrevDecl, SemanticContext, S))
 894     PrevDecl = PrevClassTemplate = 0;
 895
 896   if (PrevClassTemplate) {
 897     // Ensure that the template parameter lists are compatible.
 898     if (!TemplateParameterListsAreEqual(TemplateParams,
 899                                    PrevClassTemplate->getTemplateParameters(),
 900                                         /*Complain=*/true,
 901                                         TPL_TemplateMatch))
 902       return true;
 903
 904     // C++ [temp.class]p4:
 905     //   In a redeclaration, partial specialization, explicit
 906     //   specialization or explicit instantiation of a class template,
 907     //   the class-key shall agree in kind with the original class
 908     //   template declaration (7.1.5.3).
 909     RecordDecl *PrevRecordDecl = PrevClassTemplate->getTemplatedDecl();
 910     if (!isAcceptableTagRedeclaration(PrevRecordDecl, Kind, KWLoc, *Name)) {
 911       Diag(KWLoc, diag::err_use_with_wrong_tag)
 912         << Name
 913         << FixItHint::CreateReplacement(KWLoc, PrevRecordDecl->getKindName());
 914       Diag(PrevRecordDecl->getLocation(), diag::note_previous_use);
 915       Kind = PrevRecordDecl->getTagKind();
 916     }
 917
 918     // Check for redefinition of this class template.
 919     if (TUK == TUK_Definition) {
 920       if (TagDecl *Def = PrevRecordDecl->getDefinition()) {
 921         Diag(NameLoc, diag::err_redefinition) << Name;
 922         Diag(Def->getLocation(), diag::note_previous_definition);
 923         // FIXME: Would it make sense to try to "forget" the previous
 924         // definition, as part of error recovery?
 925         return true;
 926       }
 927     }
 928   } else if (PrevDecl && PrevDecl->isTemplateParameter()) {
 929     // Maybe we will complain about the shadowed template parameter.
 930     DiagnoseTemplateParameterShadow(NameLoc, PrevDecl);
 931     // Just pretend that we didn't see the previous declaration.
 932     PrevDecl = 0;
 933   } else if (PrevDecl) {
 934     // C++ [temp]p5:
 935     //   A class template shall not have the same name as any other
 936     //   template, class, function, object, enumeration, enumerator,
 937     //   namespace, or type in the same scope (3.3), except as specified
 938     //   in (14.5.4).
 939     Diag(NameLoc, diag::err_redefinition_different_kind) << Name;
 940     Diag(PrevDecl->getLocation(), diag::note_previous_definition);
 941     return true;
 942   }
 943
 944   // Check the template parameter list of this declaration, possibly
 945   // merging in the template parameter list from the previous class
 946   // template declaration.
 947   if (CheckTemplateParameterList(TemplateParams,
 948             PrevClassTemplate? PrevClassTemplate->getTemplateParameters() : 0,
 949                                  (SS.isSet() && SemanticContext &&
 950                                   SemanticContext->isRecord() &&
 951                                   SemanticContext->isDependentContext())
 952                                    ? TPC_ClassTemplateMember
 953                                    : TPC_ClassTemplate))
 954     Invalid = true;
 955
 956   if (SS.isSet()) {
 957     // If the name of the template was qualified, we must be defining the
 958     // template out-of-line.
 959     if (!SS.isInvalid() && !Invalid && !PrevClassTemplate &&
 960         !(TUK == TUK_Friend && CurContext->isDependentContext()))
 961       Diag(NameLoc, diag::err_member_def_does_not_match)
 962         << Name << SemanticContext << SS.getRange();
 963   }
 964
 965   CXXRecordDecl *NewClass =
 966     CXXRecordDecl::Create(Context, Kind, SemanticContext, NameLoc, Name, KWLoc,
 967                           PrevClassTemplate?
 968                             PrevClassTemplate->getTemplatedDecl() : 0,
 969                           /*DelayTypeCreation=*/true);
 970   SetNestedNameSpecifier(NewClass, SS);
 971
 972   ClassTemplateDecl *NewTemplate
 973     = ClassTemplateDecl::Create(Context, SemanticContext, NameLoc,
 974                                 DeclarationName(Name), TemplateParams,
 975                                 NewClass, PrevClassTemplate);
 976   NewClass->setDescribedClassTemplate(NewTemplate);
 977
 978   // Build the type for the class template declaration now.
 979   QualType T = NewTemplate->getInjectedClassNameSpecialization();
 980   T = Context.getInjectedClassNameType(NewClass, T);
 981   assert(T->isDependentType() && "Class template type is not dependent?");
 982   (void)T;
 983
 984   // If we are providing an explicit specialization of a member that is a
 985   // class template, make a note of that.
 986   if (PrevClassTemplate &&
 987       PrevClassTemplate->getInstantiatedFromMemberTemplate())
 988     PrevClassTemplate->setMemberSpecialization();
 989
 990   // Set the access specifier.
 991   if (!Invalid && TUK != TUK_Friend)
 992     SetMemberAccessSpecifier(NewTemplate, PrevClassTemplate, AS);
 993
 994   // Set the lexical context of these templates
 995   NewClass->setLexicalDeclContext(CurContext);
 996   NewTemplate->setLexicalDeclContext(CurContext);
 997
 998   if (TUK == TUK_Definition)
 999     NewClass->startDefinition();
1000
1001   if (Attr)
1002     ProcessDeclAttributeList(S, NewClass, Attr);
1003
1004   if (TUK != TUK_Friend)
1005     PushOnScopeChains(NewTemplate, S);
1006   else {
1007     if (PrevClassTemplate && PrevClassTemplate->getAccess() != AS_none) {
1008       NewTemplate->setAccess(PrevClassTemplate->getAccess());
1009       NewClass->setAccess(PrevClassTemplate->getAccess());
1010     }
1011
1012     NewTemplate->setObjectOfFriendDecl(/* PreviouslyDeclared = */
1013                                        PrevClassTemplate != NULL);
1014
1015     // Friend templates are visible in fairly strange ways.
1016     if (!CurContext->isDependentContext()) {
1017       DeclContext *DC = SemanticContext->getRedeclContext();
1018       DC->makeDeclVisibleInContext(NewTemplate, /* Recoverable = */ false);
1019       if (Scope *EnclosingScope = getScopeForDeclContext(S, DC))
1020         PushOnScopeChains(NewTemplate, EnclosingScope,
1021                           /* AddToContext = */ false);
1022     }
1023
1024     FriendDecl *Friend = FriendDecl::Create(Context, CurContext,
1025                                             NewClass->getLocation(),
1026                                             NewTemplate,
1027                                     /*FIXME:*/NewClass->getLocation());
1028     Friend->setAccess(AS_public);
1029     CurContext->addDecl(Friend);
1030   }
1031
1032   if (Invalid) {
1033     NewTemplate->setInvalidDecl();
1034     NewClass->setInvalidDecl();
1035   }
1036   return NewTemplate;
1037 }
1038
1039 /// \brief Diagnose the presence of a default template argument on a
1040 /// template parameter, which is ill-formed in certain contexts.
1041 ///
1042 /// \returns true if the default template argument should be dropped.
1043 static bool DiagnoseDefaultTemplateArgument(Sema &S,
1044                                             Sema::TemplateParamListContext TPC,
1045                                             SourceLocation ParamLoc,
1046                                             SourceRange DefArgRange) {
1047   switch (TPC) {
1048   case Sema::TPC_ClassTemplate:
1049     return false;
1050
1051   case Sema::TPC_FunctionTemplate:
1052   case Sema::TPC_FriendFunctionTemplateDefinition:
1053     // C++ [temp.param]p9:
1054     //   A default template-argument shall not be specified in a
1055     //   function template declaration or a function template
1056     //   definition [...]
1057     //   If a friend function template declaration specifies a default
1058     //   template-argument, that declaration shall be a definition and shall be
1059     //   the only declaration of the function template in the translation unit.
1060     // (C++98/03 doesn't have this wording; see DR226).
1061     if (!S.getLangOptions().CPlusPlus0x)
1062       S.Diag(ParamLoc,
1063              diag::ext_template_parameter_default_in_function_template)
1064         << DefArgRange;
1065     return false;
1066
1067   case Sema::TPC_ClassTemplateMember:
1068     // C++0x [temp.param]p9:
1069     //   A default template-argument shall not be specified in the
1070     //   template-parameter-lists of the definition of a member of a
1071     //   class template that appears outside of the member's class.
1072     S.Diag(ParamLoc, diag::err_template_parameter_default_template_member)
1073       << DefArgRange;
1074     return true;
1075
1076   case Sema::TPC_FriendFunctionTemplate:
1077     // C++ [temp.param]p9:
1078     //   A default template-argument shall not be specified in a
1079     //   friend template declaration.
1080     S.Diag(ParamLoc, diag::err_template_parameter_default_friend_template)
1081       << DefArgRange;
1082     return true;
1083
1084     // FIXME: C++0x [temp.param]p9 allows default template-arguments
1085     // for friend function templates if there is only a single
1086     // declaration (and it is a definition). Strange!
1087   }
1088
1089   return false;
1090 }
1091
1092 /// \brief Check for unexpanded parameter packs within the template parameters
1093 /// of a template template parameter, recursively.
1094 bool DiagnoseUnexpandedParameterPacks(Sema &S, TemplateTemplateParmDecl *TTP){
1095   TemplateParameterList *Params = TTP->getTemplateParameters();
1096   for (unsigned I = 0, N = Params->size(); I != N; ++I) {
1097     NamedDecl *P = Params->getParam(I);
1098     if (NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(P)) {
1099       if (S.DiagnoseUnexpandedParameterPack(NTTP->getLocation(),
1100                                             NTTP->getTypeSourceInfo(),
1101                                       Sema::UPPC_NonTypeTemplateParameterType))
1102         return true;
1103
1104       continue;
1105     }
1106
1107     if (TemplateTemplateParmDecl *InnerTTP
1108                                         = dyn_cast<TemplateTemplateParmDecl>(P))
1109       if (DiagnoseUnexpandedParameterPacks(S, InnerTTP))
1110         return true;
1111   }
1112
1113   return false;
1114 }
1115
1116 /// \brief Checks the validity of a template parameter list, possibly
1117 /// considering the template parameter list from a previous
1118 /// declaration.
1119 ///
1120 /// If an "old" template parameter list is provided, it must be
1121 /// equivalent (per TemplateParameterListsAreEqual) to the "new"
1122 /// template parameter list.
1123 ///
1124 /// \param NewParams Template parameter list for a new template
1125 /// declaration. This template parameter list will be updated with any
1126 /// default arguments that are carried through from the previous
1127 /// template parameter list.
1128 ///
1129 /// \param OldParams If provided, template parameter list from a
1130 /// previous declaration of the same template. Default template
1131 /// arguments will be merged from the old template parameter list to
1132 /// the new template parameter list.
1133 ///
1134 /// \param TPC Describes the context in which we are checking the given
1135 /// template parameter list.
1136 ///
1137 /// \returns true if an error occurred, false otherwise.
1138 bool Sema::CheckTemplateParameterList(TemplateParameterList *NewParams,
1139                                       TemplateParameterList *OldParams,
1140                                       TemplateParamListContext TPC) {
1141   bool Invalid = false;
1142
1143   // C++ [temp.param]p10:
1144   //   The set of default template-arguments available for use with a
1145   //   template declaration or definition is obtained by merging the
1146   //   default arguments from the definition (if in scope) and all
1147   //   declarations in scope in the same way default function
1148   //   arguments are (8.3.6).
1149   bool SawDefaultArgument = false;
1150   SourceLocation PreviousDefaultArgLoc;
1151
1152   bool SawParameterPack = false;
1153   SourceLocation ParameterPackLoc;
1154
1155   // Dummy initialization to avoid warnings.
1156   TemplateParameterList::iterator OldParam = NewParams->end();
1157   if (OldParams)
1158     OldParam = OldParams->begin();
1159
1160   bool RemoveDefaultArguments = false;
1161   for (TemplateParameterList::iterator NewParam = NewParams->begin(),
1162                                     NewParamEnd = NewParams->end();
1163        NewParam != NewParamEnd; ++NewParam) {
1164     // Variables used to diagnose redundant default arguments
1165     bool RedundantDefaultArg = false;
1166     SourceLocation OldDefaultLoc;
1167     SourceLocation NewDefaultLoc;
1168
1169     // Variables used to diagnose missing default arguments
1170     bool MissingDefaultArg = false;
1171
1172     // C++0x [temp.param]p11:
1173     //   If a template parameter of a primary class template is a template
1174     //   parameter pack, it shall be the last template parameter.
1175     if (SawParameterPack && TPC == TPC_ClassTemplate) {
1176       Diag(ParameterPackLoc,
1177            diag::err_template_param_pack_must_be_last_template_parameter);
1178       Invalid = true;
1179     }
1180
1181     if (TemplateTypeParmDecl *NewTypeParm
1182           = dyn_cast<TemplateTypeParmDecl>(*NewParam)) {
1183       // Check the presence of a default argument here.
1184       if (NewTypeParm->hasDefaultArgument() &&
1185           DiagnoseDefaultTemplateArgument(*this, TPC,
1186                                           NewTypeParm->getLocation(),
1187                NewTypeParm->getDefaultArgumentInfo()->getTypeLoc()
1188                                                        .getSourceRange()))
1189         NewTypeParm->removeDefaultArgument();
1190
1191       // Merge default arguments for template type parameters.
1192       TemplateTypeParmDecl *OldTypeParm
1193           = OldParams? cast<TemplateTypeParmDecl>(*OldParam) : 0;
1194
1195       if (NewTypeParm->isParameterPack()) {
1196         assert(!NewTypeParm->hasDefaultArgument() &&
1197                "Parameter packs can't have a default argument!");
1198         SawParameterPack = true;
1199         ParameterPackLoc = NewTypeParm->getLocation();
1200       } else if (OldTypeParm && OldTypeParm->hasDefaultArgument() &&
1201                  NewTypeParm->hasDefaultArgument()) {
1202         OldDefaultLoc = OldTypeParm->getDefaultArgumentLoc();
1203         NewDefaultLoc = NewTypeParm->getDefaultArgumentLoc();
1204         SawDefaultArgument = true;
1205         RedundantDefaultArg = true;
1206         PreviousDefaultArgLoc = NewDefaultLoc;
1207       } else if (OldTypeParm && OldTypeParm->hasDefaultArgument()) {
1208         // Merge the default argument from the old declaration to the
1209         // new declaration.
1210         SawDefaultArgument = true;
1211         NewTypeParm->setDefaultArgument(OldTypeParm->getDefaultArgumentInfo(),
1212                                         true);
1213         PreviousDefaultArgLoc = OldTypeParm->getDefaultArgumentLoc();
1214       } else if (NewTypeParm->hasDefaultArgument()) {
1215         SawDefaultArgument = true;
1216         PreviousDefaultArgLoc = NewTypeParm->getDefaultArgumentLoc();
1217       } else if (SawDefaultArgument)
1218         MissingDefaultArg = true;
1219     } else if (NonTypeTemplateParmDecl *NewNonTypeParm
1220                = dyn_cast<NonTypeTemplateParmDecl>(*NewParam)) {
1221       // Check for unexpanded parameter packs.
1222       if (DiagnoseUnexpandedParameterPack(NewNonTypeParm->getLocation(),
1223                                           NewNonTypeParm->getTypeSourceInfo(),
1224                                           UPPC_NonTypeTemplateParameterType)) {
1225         Invalid = true;
1226         continue;
1227       }
1228
1229       // Check the presence of a default argument here.
1230       if (NewNonTypeParm->hasDefaultArgument() &&
1231           DiagnoseDefaultTemplateArgument(*this, TPC,
1232                                           NewNonTypeParm->getLocation(),
1233                     NewNonTypeParm->getDefaultArgument()->getSourceRange())) {
1234         NewNonTypeParm->removeDefaultArgument();
1235       }
1236
1237       // Merge default arguments for non-type template parameters
1238       NonTypeTemplateParmDecl *OldNonTypeParm
1239         = OldParams? cast<NonTypeTemplateParmDecl>(*OldParam) : 0;
1240       if (NewNonTypeParm->isParameterPack()) {
1241         assert(!NewNonTypeParm->hasDefaultArgument() &&
1242                "Parameter packs can't have a default argument!");
1243         SawParameterPack = true;
1244         ParameterPackLoc = NewNonTypeParm->getLocation();
1245       } else if (OldNonTypeParm && OldNonTypeParm->hasDefaultArgument() &&
1246           NewNonTypeParm->hasDefaultArgument()) {
1247         OldDefaultLoc = OldNonTypeParm->getDefaultArgumentLoc();
1248         NewDefaultLoc = NewNonTypeParm->getDefaultArgumentLoc();
1249         SawDefaultArgument = true;
1250         RedundantDefaultArg = true;
1251         PreviousDefaultArgLoc = NewDefaultLoc;
1252       } else if (OldNonTypeParm && OldNonTypeParm->hasDefaultArgument()) {
1253         // Merge the default argument from the old declaration to the
1254         // new declaration.
1255         SawDefaultArgument = true;
1256         // FIXME: We need to create a new kind of "default argument"
1257         // expression that points to a previous non-type template
1258         // parameter.
1259         NewNonTypeParm->setDefaultArgument(
1260                                          OldNonTypeParm->getDefaultArgument(),
1261                                          /*Inherited=*/ true);
1262         PreviousDefaultArgLoc = OldNonTypeParm->getDefaultArgumentLoc();
1263       } else if (NewNonTypeParm->hasDefaultArgument()) {
1264         SawDefaultArgument = true;
1265         PreviousDefaultArgLoc = NewNonTypeParm->getDefaultArgumentLoc();
1266       } else if (SawDefaultArgument)
1267         MissingDefaultArg = true;
1268     } else {
1269       // Check the presence of a default argument here.
1270       TemplateTemplateParmDecl *NewTemplateParm
1271         = cast<TemplateTemplateParmDecl>(*NewParam);
1272
1273       // Check for unexpanded parameter packs, recursively.
1274       if (DiagnoseUnexpandedParameterPacks(*this, NewTemplateParm)) {
1275         Invalid = true;
1276         continue;
1277       }
1278
1279       if (NewTemplateParm->hasDefaultArgument() &&
1280           DiagnoseDefaultTemplateArgument(*this, TPC,
1281                                           NewTemplateParm->getLocation(),
1282                      NewTemplateParm->getDefaultArgument().getSourceRange()))
1283         NewTemplateParm->removeDefaultArgument();
1284
1285       // Merge default arguments for template template parameters
1286       TemplateTemplateParmDecl *OldTemplateParm
1287         = OldParams? cast<TemplateTemplateParmDecl>(*OldParam) : 0;
1288       if (NewTemplateParm->isParameterPack()) {
1289         assert(!NewTemplateParm->hasDefaultArgument() &&
1290                "Parameter packs can't have a default argument!");
1291         SawParameterPack = true;
1292         ParameterPackLoc = NewTemplateParm->getLocation();
1293       } else if (OldTemplateParm && OldTemplateParm->hasDefaultArgument() &&
1294           NewTemplateParm->hasDefaultArgument()) {
1295         OldDefaultLoc = OldTemplateParm->getDefaultArgument().getLocation();
1296         NewDefaultLoc = NewTemplateParm->getDefaultArgument().getLocation();
1297         SawDefaultArgument = true;
1298         RedundantDefaultArg = true;
1299         PreviousDefaultArgLoc = NewDefaultLoc;
1300       } else if (OldTemplateParm && OldTemplateParm->hasDefaultArgument()) {
1301         // Merge the default argument from the old declaration to the
1302         // new declaration.
1303         SawDefaultArgument = true;
1304         // FIXME: We need to create a new kind of "default argument" expression
1305         // that points to a previous template template parameter.
1306         NewTemplateParm->setDefaultArgument(
1307                                           OldTemplateParm->getDefaultArgument(),
1308                                           /*Inherited=*/ true);
1309         PreviousDefaultArgLoc
1310           = OldTemplateParm->getDefaultArgument().getLocation();
1311       } else if (NewTemplateParm->hasDefaultArgument()) {
1312         SawDefaultArgument = true;
1313         PreviousDefaultArgLoc
1314           = NewTemplateParm->getDefaultArgument().getLocation();
1315       } else if (SawDefaultArgument)
1316         MissingDefaultArg = true;
1317     }
1318
1319     if (RedundantDefaultArg) {
1320       // C++ [temp.param]p12:
1321       //   A template-parameter shall not be given default arguments
1322       //   by two different declarations in the same scope.
1323       Diag(NewDefaultLoc, diag::err_template_param_default_arg_redefinition);
1324       Diag(OldDefaultLoc, diag::note_template_param_prev_default_arg);
1325       Invalid = true;
1326     } else if (MissingDefaultArg && TPC != TPC_FunctionTemplate) {
1327       // C++ [temp.param]p11:
1328       //   If a template-parameter of a class template has a default
1329       //   template-argument, each subsequent template-parameter shall either
1330       //   have a default template-argument supplied or be a template parameter
1331       //   pack.
1332       Diag((*NewParam)->getLocation(),
1333            diag::err_template_param_default_arg_missing);
1334       Diag(PreviousDefaultArgLoc, diag::note_template_param_prev_default_arg);
1335       Invalid = true;
1336       RemoveDefaultArguments = true;
1337     }
1338
1339     // If we have an old template parameter list that we're merging
1340     // in, move on to the next parameter.
1341     if (OldParams)
1342       ++OldParam;
1343   }
1344
1345   // We were missing some default arguments at the end of the list, so remove
1346   // all of the default arguments.
1347   if (RemoveDefaultArguments) {
1348     for (TemplateParameterList::iterator NewParam = NewParams->begin(),
1349                                       NewParamEnd = NewParams->end();
1350          NewParam != NewParamEnd; ++NewParam) {
1351       if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(*NewParam))
1352         TTP->removeDefaultArgument();
1353       else if (NonTypeTemplateParmDecl *NTTP
1354                                 = dyn_cast<NonTypeTemplateParmDecl>(*NewParam))
1355         NTTP->removeDefaultArgument();
1356       else
1357         cast<TemplateTemplateParmDecl>(*NewParam)->removeDefaultArgument();
1358     }
1359   }
1360
1361   return Invalid;
1362 }
1363
1364 namespace {
1365
1366 /// A class which looks for a use of a certain level of template
1367 /// parameter.
1368 struct DependencyChecker : RecursiveASTVisitor<DependencyChecker> {
1369   typedef RecursiveASTVisitor<DependencyChecker> super;
1370
1371   unsigned Depth;
1372   bool Match;
1373
1374   DependencyChecker(TemplateParameterList *Params) : Match(false) {
1375     NamedDecl *ND = Params->getParam(0);
1376     if (TemplateTypeParmDecl *PD = dyn_cast<TemplateTypeParmDecl>(ND)) {
1377       Depth = PD->getDepth();
1378     } else if (NonTypeTemplateParmDecl *PD =
1379                  dyn_cast<NonTypeTemplateParmDecl>(ND)) {
1380       Depth = PD->getDepth();
1381     } else {
1382       Depth = cast<TemplateTemplateParmDecl>(ND)->getDepth();
1383     }
1384   }
1385
1386   bool Matches(unsigned ParmDepth) {
1387     if (ParmDepth >= Depth) {
1388       Match = true;
1389       return true;
1390     }
1391     return false;
1392   }
1393
1394   bool VisitTemplateTypeParmType(const TemplateTypeParmType *T) {
1395     return !Matches(T->getDepth());
1396   }
1397
1398   bool TraverseTemplateName(TemplateName N) {
1399     if (TemplateTemplateParmDecl *PD =
1400           dyn_cast_or_null<TemplateTemplateParmDecl>(N.getAsTemplateDecl()))
1401       if (Matches(PD->getDepth())) return false;
1402     return super::TraverseTemplateName(N);
1403   }
1404
1405   bool VisitDeclRefExpr(DeclRefExpr *E) {
1406     if (NonTypeTemplateParmDecl *PD =
1407           dyn_cast<NonTypeTemplateParmDecl>(E->getDecl())) {
1408       if (PD->getDepth() == Depth) {
1409         Match = true;
1410         return false;
1411       }
1412     }
1413     return super::VisitDeclRefExpr(E);
1414   }
1415 };
1416 }
1417
1418 /// Determines whether a template-id depends on the given parameter
1419 /// list.
1420 static bool
1421 DependsOnTemplateParameters(const TemplateSpecializationType *TemplateId,
1422                             TemplateParameterList *Params) {
1423   DependencyChecker Checker(Params);
1424   Checker.TraverseType(QualType(TemplateId, 0));
1425   return Checker.Match;
1426 }
1427
1428 /// \brief Match the given template parameter lists to the given scope
1429 /// specifier, returning the template parameter list that applies to the
1430 /// name.
1431 ///
1432 /// \param DeclStartLoc the start of the declaration that has a scope
1433 /// specifier or a template parameter list.
1434 ///
1435 /// \param SS the scope specifier that will be matched to the given template
1436 /// parameter lists. This scope specifier precedes a qualified name that is
1437 /// being declared.
1438 ///
1439 /// \param ParamLists the template parameter lists, from the outermost to the
1440 /// innermost template parameter lists.
1441 ///
1442 /// \param NumParamLists the number of template parameter lists in ParamLists.
1443 ///
1444 /// \param IsFriend Whether to apply the slightly different rules for
1445 /// matching template parameters to scope specifiers in friend
1446 /// declarations.
1447 ///
1448 /// \param IsExplicitSpecialization will be set true if the entity being
1449 /// declared is an explicit specialization, false otherwise.
1450 ///
1451 /// \returns the template parameter list, if any, that corresponds to the
1452 /// name that is preceded by the scope specifier @p SS. This template
1453 /// parameter list may be have template parameters (if we're declaring a
1454 /// template) or may have no template parameters (if we're declaring a
1455 /// template specialization), or may be NULL (if we were's declaring isn't
1456 /// itself a template).
1457 TemplateParameterList *
1458 Sema::MatchTemplateParametersToScopeSpecifier(SourceLocation DeclStartLoc,
1459                                               const CXXScopeSpec &SS,
1460                                           TemplateParameterList **ParamLists,
1461                                               unsigned NumParamLists,
1462                                               bool IsFriend,
1463                                               bool &IsExplicitSpecialization,
1464                                               bool &Invalid) {
1465   IsExplicitSpecialization = false;
1466
1467   // Find the template-ids that occur within the nested-name-specifier. These
1468   // template-ids will match up with the template parameter lists.
1469   llvm::SmallVector<const TemplateSpecializationType *, 4>
1470     TemplateIdsInSpecifier;
1471   llvm::SmallVector<ClassTemplateSpecializationDecl *, 4>
1472     ExplicitSpecializationsInSpecifier;
1473   for (NestedNameSpecifier *NNS = (NestedNameSpecifier *)SS.getScopeRep();
1474        NNS; NNS = NNS->getPrefix()) {
1475     const Type *T = NNS->getAsType();
1476     if (!T) break;
1477
1478     // C++0x [temp.expl.spec]p17:
1479     //   A member or a member template may be nested within many
1480     //   enclosing class templates. In an explicit specialization for
1481     //   such a member, the member declaration shall be preceded by a
1482     //   template<> for each enclosing class template that is
1483     //   explicitly specialized.
1484     //
1485     // Following the existing practice of GNU and EDG, we allow a typedef of a
1486     // template specialization type.
1487     while (const TypedefType *TT = dyn_cast<TypedefType>(T))
1488       T = TT->getDecl()->getUnderlyingType().getTypePtr();
1489
1490     if (const TemplateSpecializationType *SpecType
1491                                   = dyn_cast<TemplateSpecializationType>(T)) {
1492       TemplateDecl *Template = SpecType->getTemplateName().getAsTemplateDecl();
1493       if (!Template)
1494         continue; // FIXME: should this be an error? probably...
1495
1496       if (const RecordType *Record = SpecType->getAs<RecordType>()) {
1497         ClassTemplateSpecializationDecl *SpecDecl
1498           = cast<ClassTemplateSpecializationDecl>(Record->getDecl());
1499         // If the nested name specifier refers to an explicit specialization,
1500         // we don't need a template<> header.
1501         if (SpecDecl->getSpecializationKind() == TSK_ExplicitSpecialization) {
1502           ExplicitSpecializationsInSpecifier.push_back(SpecDecl);
1503           continue;
1504         }
1505       }
1506
1507       TemplateIdsInSpecifier.push_back(SpecType);
1508     }
1509   }
1510
1511   // Reverse the list of template-ids in the scope specifier, so that we can
1512   // more easily match up the template-ids and the template parameter lists.
1513   std::reverse(TemplateIdsInSpecifier.begin(), TemplateIdsInSpecifier.end());
1514
1515   SourceLocation FirstTemplateLoc = DeclStartLoc;
1516   if (NumParamLists)
1517     FirstTemplateLoc = ParamLists[0]->getTemplateLoc();
1518
1519   // Match the template-ids found in the specifier to the template parameter
1520   // lists.
1521   unsigned ParamIdx = 0, TemplateIdx = 0;
1522   for (unsigned NumTemplateIds = TemplateIdsInSpecifier.size();
1523        TemplateIdx != NumTemplateIds; ++TemplateIdx) {
1524     const TemplateSpecializationType *TemplateId
1525       = TemplateIdsInSpecifier[TemplateIdx];
1526     bool DependentTemplateId = TemplateId->isDependentType();
1527
1528     // In friend declarations we can have template-ids which don't
1529     // depend on the corresponding template parameter lists.  But
1530     // assume that empty parameter lists are supposed to match this
1531     // template-id.
1532     if (IsFriend && ParamIdx < NumParamLists && ParamLists[ParamIdx]->size()) {
1533       if (!DependentTemplateId ||
1534           !DependsOnTemplateParameters(TemplateId, ParamLists[ParamIdx]))
1535         continue;
1536     }
1537
1538     if (ParamIdx >= NumParamLists) {
1539       // We have a template-id without a corresponding template parameter
1540       // list.
1541
1542       // ...which is fine if this is a friend declaration.
1543       if (IsFriend) {
1544         IsExplicitSpecialization = true;
1545         break;
1546       }
1547
1548       if (DependentTemplateId) {
1549         // FIXME: the location information here isn't great.
1550         Diag(SS.getRange().getBegin(),
1551              diag::err_template_spec_needs_template_parameters)
1552           << QualType(TemplateId, 0)
1553           << SS.getRange();
1554         Invalid = true;
1555       } else {
1556         Diag(SS.getRange().getBegin(), diag::err_template_spec_needs_header)
1557           << SS.getRange()
1558           << FixItHint::CreateInsertion(FirstTemplateLoc, "template<> ");
1559         IsExplicitSpecialization = true;
1560       }
1561       return 0;
1562     }
1563
1564     // Check the template parameter list against its corresponding template-id.
1565     if (DependentTemplateId) {
1566       TemplateParameterList *ExpectedTemplateParams = 0;
1567
1568       // Are there cases in (e.g.) friends where this won't match?
1569       if (const InjectedClassNameType *Injected
1570             = TemplateId->getAs<InjectedClassNameType>()) {
1571         CXXRecordDecl *Record = Injected->getDecl();
1572         if (ClassTemplatePartialSpecializationDecl *Partial =
1573               dyn_cast<ClassTemplatePartialSpecializationDecl>(Record))
1574           ExpectedTemplateParams = Partial->getTemplateParameters();
1575         else
1576           ExpectedTemplateParams = Record->getDescribedClassTemplate()
1577             ->getTemplateParameters();
1578       }
1579
1580       if (ExpectedTemplateParams)
1581         TemplateParameterListsAreEqual(ParamLists[ParamIdx],
1582                                        ExpectedTemplateParams,
1583                                        true, TPL_TemplateMatch);
1584
1585       CheckTemplateParameterList(ParamLists[ParamIdx], 0,
1586                                  TPC_ClassTemplateMember);
1587     } else if (ParamLists[ParamIdx]->size() > 0)
1588       Diag(ParamLists[ParamIdx]->getTemplateLoc(),
1589            diag::err_template_param_list_matches_nontemplate)
1590         << TemplateId
1591         << ParamLists[ParamIdx]->getSourceRange();
1592     else
1593       IsExplicitSpecialization = true;
1594
1595     ++ParamIdx;
1596   }
1597
1598   // If there were at least as many template-ids as there were template
1599   // parameter lists, then there are no template parameter lists remaining for
1600   // the declaration itself.
1601   if (ParamIdx >= NumParamLists)
1602     return 0;
1603
1604   // If there were too many template parameter lists, complain about that now.
1605   if (ParamIdx != NumParamLists - 1) {
1606     while (ParamIdx < NumParamLists - 1) {
1607       bool isExplicitSpecHeader = ParamLists[ParamIdx]->size() == 0;
1608       Diag(ParamLists[ParamIdx]->getTemplateLoc(),
1609            isExplicitSpecHeader? diag::warn_template_spec_extra_headers
1610                                : diag::err_template_spec_extra_headers)
1611         << SourceRange(ParamLists[ParamIdx]->getTemplateLoc(),
1612                        ParamLists[ParamIdx]->getRAngleLoc());
1613
1614       if (isExplicitSpecHeader && !ExplicitSpecializationsInSpecifier.empty()) {
1615         Diag(ExplicitSpecializationsInSpecifier.back()->getLocation(),
1616              diag::note_explicit_template_spec_does_not_need_header)
1617           << ExplicitSpecializationsInSpecifier.back();
1618         ExplicitSpecializationsInSpecifier.pop_back();
1619       }
1620
1621       // We have a template parameter list with no corresponding scope, which
1622       // means that the resulting template declaration can't be instantiated
1623       // properly (we'll end up with dependent nodes when we shouldn't).
1624       if (!isExplicitSpecHeader)
1625         Invalid = true;
1626
1627       ++ParamIdx;
1628     }
1629   }
1630
1631   // Return the last template parameter list, which corresponds to the
1632   // entity being declared.
1633   return ParamLists[NumParamLists - 1];
1634 }
1635
1636 QualType Sema::CheckTemplateIdType(TemplateName Name,
1637                                    SourceLocation TemplateLoc,
1638                               const TemplateArgumentListInfo &TemplateArgs) {
1639   TemplateDecl *Template = Name.getAsTemplateDecl();
1640   if (!Template) {
1641     // The template name does not resolve to a template, so we just
1642     // build a dependent template-id type.
1643     return Context.getTemplateSpecializationType(Name, TemplateArgs);
1644   }
1645
1646   // Check that the template argument list is well-formed for this
1647   // template.
1648   llvm::SmallVector<TemplateArgument, 4> Converted;
1649   if (CheckTemplateArgumentList(Template, TemplateLoc, TemplateArgs,
1650                                 false, Converted))
1651     return QualType();
1652
1653   assert((Converted.size() == Template->getTemplateParameters()->size()) &&
1654          "Converted template argument list is too short!");
1655
1656   QualType CanonType;
1657
1658   if (Name.isDependent() ||
1659       TemplateSpecializationType::anyDependentTemplateArguments(
1660                                                       TemplateArgs)) {
1661     // This class template specialization is a dependent
1662     // type. Therefore, its canonical type is another class template
1663     // specialization type that contains all of the converted
1664     // arguments in canonical form. This ensures that, e.g., A<T> and
1665     // A<T, T> have identical types when A is declared as:
1666     //
1667     //   template<typename T, typename U = T> struct A;
1668     TemplateName CanonName = Context.getCanonicalTemplateName(Name);
1669     CanonType = Context.getTemplateSpecializationType(CanonName,
1670                                                       Converted.data(),
1671                                                       Converted.size());
1672
1673     // FIXME: CanonType is not actually the canonical type, and unfortunately
1674     // it is a TemplateSpecializationType that we will never use again.
1675     // In the future, we need to teach getTemplateSpecializationType to only
1676     // build the canonical type and return that to us.
1677     CanonType = Context.getCanonicalType(CanonType);
1678
1679     // This might work out to be a current instantiation, in which
1680     // case the canonical type needs to be the InjectedClassNameType.
1681     //
1682     // TODO: in theory this could be a simple hashtable lookup; most
1683     // changes to CurContext don't change the set of current
1684     // instantiations.
1685     if (isa<ClassTemplateDecl>(Template)) {
1686       for (DeclContext *Ctx = CurContext; Ctx; Ctx = Ctx->getLookupParent()) {
1687         // If we get out to a namespace, we're done.
1688         if (Ctx->isFileContext()) break;
1689
1690         // If this isn't a record, keep looking.
1691         CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(Ctx);
1692         if (!Record) continue;
1693
1694         // Look for one of the two cases with InjectedClassNameTypes
1695         // and check whether it's the same template.
1696         if (!isa<ClassTemplatePartialSpecializationDecl>(Record) &&
1697             !Record->getDescribedClassTemplate())
1698           continue;
1699
1700         // Fetch the injected class name type and check whether its
1701         // injected type is equal to the type we just built.
1702         QualType ICNT = Context.getTypeDeclType(Record);
1703         QualType Injected = cast<InjectedClassNameType>(ICNT)
1704           ->getInjectedSpecializationType();
1705
1706         if (CanonType != Injected->getCanonicalTypeInternal())
1707           continue;
1708
1709         // If so, the canonical type of this TST is the injected
1710         // class name type of the record we just found.
1711         assert(ICNT.isCanonical());
1712         CanonType = ICNT;
1713         break;
1714       }
1715     }
1716   } else if (ClassTemplateDecl *ClassTemplate
1717                = dyn_cast<ClassTemplateDecl>(Template)) {
1718     // Find the class template specialization declaration that
1719     // corresponds to these arguments.
1720     void *InsertPos = 0;
1721     ClassTemplateSpecializationDecl *Decl
1722       = ClassTemplate->findSpecialization(Converted.data(), Converted.size(),
1723                                           InsertPos);
1724     if (!Decl) {
1725       // This is the first time we have referenced this class template
1726       // specialization. Create the canonical declaration and add it to
1727       // the set of specializations.
1728       Decl = ClassTemplateSpecializationDecl::Create(Context,
1729                             ClassTemplate->getTemplatedDecl()->getTagKind(),
1730                                                 ClassTemplate->getDeclContext(),
1731                                                 ClassTemplate->getLocation(),
1732                                                      ClassTemplate,
1733                                                      Converted.data(),
1734                                                      Converted.size(), 0);
1735       ClassTemplate->AddSpecialization(Decl, InsertPos);
1736       Decl->setLexicalDeclContext(CurContext);
1737     }
1738
1739     CanonType = Context.getTypeDeclType(Decl);
1740     assert(isa<RecordType>(CanonType) &&
1741            "type of non-dependent specialization is not a RecordType");
1742   }
1743
1744   // Build the fully-sugared type for this class template
1745   // specialization, which refers back to the class template
1746   // specialization we created or found.
1747   return Context.getTemplateSpecializationType(Name, TemplateArgs, CanonType);
1748 }
1749
1750 TypeResult
1751 Sema::ActOnTemplateIdType(TemplateTy TemplateD, SourceLocation TemplateLoc,
1752                           SourceLocation LAngleLoc,
1753                           ASTTemplateArgsPtr TemplateArgsIn,
1754                           SourceLocation RAngleLoc) {
1755   TemplateName Template = TemplateD.getAsVal<TemplateName>();
1756
1757   // Translate the parser's template argument list in our AST format.
1758   TemplateArgumentListInfo TemplateArgs(LAngleLoc, RAngleLoc);
1759   translateTemplateArguments(TemplateArgsIn, TemplateArgs);
1760
1761   QualType Result = CheckTemplateIdType(Template, TemplateLoc, TemplateArgs);
1762   TemplateArgsIn.release();
1763
1764   if (Result.isNull())
1765     return true;
1766
1767   TypeSourceInfo *DI = Context.CreateTypeSourceInfo(Result);
1768   TemplateSpecializationTypeLoc TL
1769     = cast<TemplateSpecializationTypeLoc>(DI->getTypeLoc());
1770   TL.setTemplateNameLoc(TemplateLoc);
1771   TL.setLAngleLoc(LAngleLoc);
1772   TL.setRAngleLoc(RAngleLoc);
1773   for (unsigned i = 0, e = TL.getNumArgs(); i != e; ++i)
1774     TL.setArgLocInfo(i, TemplateArgs[i].getLocInfo());
1775
1776   return CreateParsedType(Result, DI);
1777 }
1778
1779 TypeResult Sema::ActOnTagTemplateIdType(CXXScopeSpec &SS,
1780                                         TypeResult TypeResult,
1781                                         TagUseKind TUK,
1782                                         TypeSpecifierType TagSpec,
1783                                         SourceLocation TagLoc) {
1784   if (TypeResult.isInvalid())
1785     return ::TypeResult();
1786
1787   TypeSourceInfo *DI;
1788   QualType Type = GetTypeFromParser(TypeResult.get(), &DI);
1789
1790   // Verify the tag specifier.
1791   TagTypeKind TagKind = TypeWithKeyword::getTagTypeKindForTypeSpec(TagSpec);
1792
1793   if (const RecordType *RT = Type->getAs<RecordType>()) {
1794     RecordDecl *D = RT->getDecl();
1795
1796     IdentifierInfo *Id = D->getIdentifier();
1797     assert(Id && "templated class must have an identifier");
1798
1799     if (!isAcceptableTagRedeclaration(D, TagKind, TagLoc, *Id)) {
1800       Diag(TagLoc, diag::err_use_with_wrong_tag)
1801         << Type
1802         << FixItHint::CreateReplacement(SourceRange(TagLoc), D->getKindName());
1803       Diag(D->getLocation(), diag::note_previous_use);
1804     }
1805   }
1806
1807   ElaboratedTypeKeyword Keyword
1808     = TypeWithKeyword::getKeywordForTagTypeKind(TagKind);
1809   QualType ElabType = Context.getElaboratedType(Keyword, /*NNS=*/0, Type);
1810
1811   TypeSourceInfo *ElabDI = Context.CreateTypeSourceInfo(ElabType);
1812   ElaboratedTypeLoc TL = cast<ElaboratedTypeLoc>(ElabDI->getTypeLoc());
1813   TL.setKeywordLoc(TagLoc);
1814   TL.setQualifierRange(SS.getRange());
1815   TL.getNamedTypeLoc().initializeFullCopy(DI->getTypeLoc());
1816   return CreateParsedType(ElabType, ElabDI);
1817 }
1818
1819 ExprResult Sema::BuildTemplateIdExpr(const CXXScopeSpec &SS,
1820                                                  LookupResult &R,
1821                                                  bool RequiresADL,
1822                                  const TemplateArgumentListInfo &TemplateArgs) {
1823   // FIXME: Can we do any checking at this point? I guess we could check the
1824   // template arguments that we have against the template name, if the template
1825   // name refers to a single template. That's not a terribly common case,
1826   // though.
1827   // foo<int> could identify a single function unambiguously
1828   // This approach does NOT work, since f<int>(1);
1829   // gets resolved prior to resorting to overload resolution
1830   // i.e., template<class T> void f(double);
1831   //       vs template<class T, class U> void f(U);
1832
1833   // These should be filtered out by our callers.
1834   assert(!R.empty() && "empty lookup results when building templateid");
1835   assert(!R.isAmbiguous() && "ambiguous lookup when building templateid");
1836
1837   NestedNameSpecifier *Qualifier = 0;
1838   SourceRange QualifierRange;
1839   if (SS.isSet()) {
1840     Qualifier = static_cast<NestedNameSpecifier*>(SS.getScopeRep());
1841     QualifierRange = SS.getRange();
1842   }
1843
1844   // We don't want lookup warnings at this point.
1845   R.suppressDiagnostics();
1846
1847   UnresolvedLookupExpr *ULE
1848     = UnresolvedLookupExpr::Create(Context, R.getNamingClass(),
1849                                    Qualifier, QualifierRange,
1850                                    R.getLookupNameInfo(),
1851                                    RequiresADL, TemplateArgs,
1852                                    R.begin(), R.end());
1853
1854   return Owned(ULE);
1855 }
1856
1857 // We actually only call this from template instantiation.
1858 ExprResult
1859 Sema::BuildQualifiedTemplateIdExpr(CXXScopeSpec &SS,
1860                                    const DeclarationNameInfo &NameInfo,
1861                              const TemplateArgumentListInfo &TemplateArgs) {
1862   DeclContext *DC;
1863   if (!(DC = computeDeclContext(SS, false)) ||
1864       DC->isDependentContext() ||
1865       RequireCompleteDeclContext(SS, DC))
1866     return BuildDependentDeclRefExpr(SS, NameInfo, &TemplateArgs);
1867
1868   bool MemberOfUnknownSpecialization;
1869   LookupResult R(*this, NameInfo, LookupOrdinaryName);
1870   LookupTemplateName(R, (Scope*) 0, SS, QualType(), /*Entering*/ false,
1871                      MemberOfUnknownSpecialization);
1872
1873   if (R.isAmbiguous())
1874     return ExprError();
1875
1876   if (R.empty()) {
1877     Diag(NameInfo.getLoc(), diag::err_template_kw_refers_to_non_template)
1878       << NameInfo.getName() << SS.getRange();
1879     return ExprError();
1880   }
1881
1882   if (ClassTemplateDecl *Temp = R.getAsSingle<ClassTemplateDecl>()) {
1883     Diag(NameInfo.getLoc(), diag::err_template_kw_refers_to_class_template)
1884       << (NestedNameSpecifier*) SS.getScopeRep()
1885       << NameInfo.getName() << SS.getRange();
1886     Diag(Temp->getLocation(), diag::note_referenced_class_template);
1887     return ExprError();
1888   }
1889
1890   return BuildTemplateIdExpr(SS, R, /* ADL */ false, TemplateArgs);
1891 }
1892
1893 /// \brief Form a dependent template name.
1894 ///
1895 /// This action forms a dependent template name given the template
1896 /// name and its (presumably dependent) scope specifier. For
1897 /// example, given "MetaFun::template apply", the scope specifier \p
1898 /// SS will be "MetaFun::", \p TemplateKWLoc contains the location
1899 /// of the "template" keyword, and "apply" is the \p Name.
1900 TemplateNameKind Sema::ActOnDependentTemplateName(Scope *S,
1901                                                   SourceLocation TemplateKWLoc,
1902                                                   CXXScopeSpec &SS,
1903                                                   UnqualifiedId &Name,
1904                                                   ParsedType ObjectType,
1905                                                   bool EnteringContext,
1906                                                   TemplateTy &Result) {
1907   if (TemplateKWLoc.isValid() && S && !S->getTemplateParamParent() &&
1908       !getLangOptions().CPlusPlus0x)
1909     Diag(TemplateKWLoc, diag::ext_template_outside_of_template)
1910       << FixItHint::CreateRemoval(TemplateKWLoc);
1911
1912   DeclContext *LookupCtx = 0;
1913   if (SS.isSet())
1914     LookupCtx = computeDeclContext(SS, EnteringContext);
1915   if (!LookupCtx && ObjectType)
1916     LookupCtx = computeDeclContext(ObjectType.get());
1917   if (LookupCtx) {
1918     // C++0x [temp.names]p5:
1919     //   If a name prefixed by the keyword template is not the name of
1920     //   a template, the program is ill-formed. [Note: the keyword
1921     //   template may not be applied to non-template members of class
1922     //   templates. -end note ] [ Note: as is the case with the
1923     //   typename prefix, the template prefix is allowed in cases
1924     //   where it is not strictly necessary; i.e., when the
1925     //   nested-name-specifier or the expression on the left of the ->
1926     //   or . is not dependent on a template-parameter, or the use
1927     //   does not appear in the scope of a template. -end note]
1928     //
1929     // Note: C++03 was more strict here, because it banned the use of
1930     // the "template" keyword prior to a template-name that was not a
1931     // dependent name. C++ DR468 relaxed this requirement (the
1932     // "template" keyword is now permitted). We follow the C++0x
1933     // rules, even in C++03 mode with a warning, retroactively applying the DR.
1934     bool MemberOfUnknownSpecialization;
1935     TemplateNameKind TNK = isTemplateName(0, SS, TemplateKWLoc.isValid(), Name,
1936                                           ObjectType, EnteringContext, Result,
1937                                           MemberOfUnknownSpecialization);
1938     if (TNK == TNK_Non_template && LookupCtx->isDependentContext() &&
1939         isa<CXXRecordDecl>(LookupCtx) &&
1940         cast<CXXRecordDecl>(LookupCtx)->hasAnyDependentBases()) {
1941       // This is a dependent template. Handle it below.
1942     } else if (TNK == TNK_Non_template) {
1943       Diag(Name.getSourceRange().getBegin(),
1944            diag::err_template_kw_refers_to_non_template)
1945         << GetNameFromUnqualifiedId(Name).getName()
1946         << Name.getSourceRange()
1947         << TemplateKWLoc;
1948       return TNK_Non_template;
1949     } else {
1950       // We found something; return it.
1951       return TNK;
1952     }
1953   }
1954
1955   NestedNameSpecifier *Qualifier
1956     = static_cast<NestedNameSpecifier *>(SS.getScopeRep());
1957
1958   switch (Name.getKind()) {
1959   case UnqualifiedId::IK_Identifier:
1960     Result = TemplateTy::make(Context.getDependentTemplateName(Qualifier,
1961                                                               Name.Identifier));
1962     return TNK_Dependent_template_name;
1963
1964   case UnqualifiedId::IK_OperatorFunctionId:
1965     Result = TemplateTy::make(Context.getDependentTemplateName(Qualifier,
1966                                              Name.OperatorFunctionId.Operator));
1967     return TNK_Dependent_template_name;
1968
1969   case UnqualifiedId::IK_LiteralOperatorId:
1970     assert(false && "We don't support these; Parse shouldn't have allowed propagation");
1971
1972   default:
1973     break;
1974   }
1975
1976   Diag(Name.getSourceRange().getBegin(),
1977        diag::err_template_kw_refers_to_non_template)
1978     << GetNameFromUnqualifiedId(Name).getName()
1979     << Name.getSourceRange()
1980     << TemplateKWLoc;
1981   return TNK_Non_template;
1982 }
1983
1984 bool Sema::CheckTemplateTypeArgument(TemplateTypeParmDecl *Param,
1985                                      const TemplateArgumentLoc &AL,
1986                           llvm::SmallVectorImpl<TemplateArgument> &Converted) {
1987   const TemplateArgument &Arg = AL.getArgument();
1988
1989   // Check template type parameter.
1990   switch(Arg.getKind()) {
1991   case TemplateArgument::Type:
1992     // C++ [temp.arg.type]p1:
1993     //   A template-argument for a template-parameter which is a
1994     //   type shall be a type-id.
1995     break;
1996   case TemplateArgument::Template: {
1997     // We have a template type parameter but the template argument
1998     // is a template without any arguments.
1999     SourceRange SR = AL.getSourceRange();
2000     TemplateName Name = Arg.getAsTemplate();
2001     Diag(SR.getBegin(), diag::err_template_missing_args)
2002       << Name << SR;
2003     if (TemplateDecl *Decl = Name.getAsTemplateDecl())
2004       Diag(Decl->getLocation(), diag::note_template_decl_here);
2005
2006     return true;
2007   }
2008   default: {
2009     // We have a template type parameter but the template argument
2010     // is not a type.
2011     SourceRange SR = AL.getSourceRange();
2012     Diag(SR.getBegin(), diag::err_template_arg_must_be_type) << SR;
2013     Diag(Param->getLocation(), diag::note_template_param_here);
2014
2015     return true;
2016   }
2017   }
2018
2019   if (CheckTemplateArgument(Param, AL.getTypeSourceInfo()))
2020     return true;
2021
2022   // Add the converted template type argument.
2023   Converted.push_back(
2024                  TemplateArgument(Context.getCanonicalType(Arg.getAsType())));
2025   return false;
2026 }
2027
2028 /// \brief Substitute template arguments into the default template argument for
2029 /// the given template type parameter.
2030 ///
2031 /// \param SemaRef the semantic analysis object for which we are performing
2032 /// the substitution.
2033 ///
2034 /// \param Template the template that we are synthesizing template arguments
2035 /// for.
2036 ///
2037 /// \param TemplateLoc the location of the template name that started the
2038 /// template-id we are checking.
2039 ///
2040 /// \param RAngleLoc the location of the right angle bracket ('>') that
2041 /// terminates the template-id.
2042 ///
2043 /// \param Param the template template parameter whose default we are
2044 /// substituting into.
2045 ///
2046 /// \param Converted the list of template arguments provided for template
2047 /// parameters that precede \p Param in the template parameter list.
2048 ///
2049 /// \returns the substituted template argument, or NULL if an error occurred.
2050 static TypeSourceInfo *
2051 SubstDefaultTemplateArgument(Sema &SemaRef,
2052                              TemplateDecl *Template,
2053                              SourceLocation TemplateLoc,
2054                              SourceLocation RAngleLoc,
2055                              TemplateTypeParmDecl *Param,
2056                          llvm::SmallVectorImpl<TemplateArgument> &Converted) {
2057   TypeSourceInfo *ArgType = Param->getDefaultArgumentInfo();
2058
2059   // If the argument type is dependent, instantiate it now based
2060   // on the previously-computed template arguments.
2061   if (ArgType->getType()->isDependentType()) {
2062     TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2063                                       Converted.data(), Converted.size());
2064
2065     MultiLevelTemplateArgumentList AllTemplateArgs
2066       = SemaRef.getTemplateInstantiationArgs(Template, &TemplateArgs);
2067
2068     Sema::InstantiatingTemplate Inst(SemaRef, TemplateLoc,
2069                                      Template, Converted.data(),
2070                                      Converted.size(),
2071                                      SourceRange(TemplateLoc, RAngleLoc));
2072
2073     ArgType = SemaRef.SubstType(ArgType, AllTemplateArgs,
2074                                 Param->getDefaultArgumentLoc(),
2075                                 Param->getDeclName());
2076   }
2077
2078   return ArgType;
2079 }
2080
2081 /// \brief Substitute template arguments into the default template argument for
2082 /// the given non-type template parameter.
2083 ///
2084 /// \param SemaRef the semantic analysis object for which we are performing
2085 /// the substitution.
2086 ///
2087 /// \param Template the template that we are synthesizing template arguments
2088 /// for.
2089 ///
2090 /// \param TemplateLoc the location of the template name that started the
2091 /// template-id we are checking.
2092 ///
2093 /// \param RAngleLoc the location of the right angle bracket ('>') that
2094 /// terminates the template-id.
2095 ///
2096 /// \param Param the non-type template parameter whose default we are
2097 /// substituting into.
2098 ///
2099 /// \param Converted the list of template arguments provided for template
2100 /// parameters that precede \p Param in the template parameter list.
2101 ///
2102 /// \returns the substituted template argument, or NULL if an error occurred.
2103 static ExprResult
2104 SubstDefaultTemplateArgument(Sema &SemaRef,
2105                              TemplateDecl *Template,
2106                              SourceLocation TemplateLoc,
2107                              SourceLocation RAngleLoc,
2108                              NonTypeTemplateParmDecl *Param,
2109                         llvm::SmallVectorImpl<TemplateArgument> &Converted) {
2110   TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2111                                     Converted.data(), Converted.size());
2112
2113   MultiLevelTemplateArgumentList AllTemplateArgs
2114     = SemaRef.getTemplateInstantiationArgs(Template, &TemplateArgs);
2115
2116   Sema::InstantiatingTemplate Inst(SemaRef, TemplateLoc,
2117                                    Template, Converted.data(),
2118                                    Converted.size(),
2119                                    SourceRange(TemplateLoc, RAngleLoc));
2120
2121   return SemaRef.SubstExpr(Param->getDefaultArgument(), AllTemplateArgs);
2122 }
2123
2124 /// \brief Substitute template arguments into the default template argument for
2125 /// the given template template parameter.
2126 ///
2127 /// \param SemaRef the semantic analysis object for which we are performing
2128 /// the substitution.
2129 ///
2130 /// \param Template the template that we are synthesizing template arguments
2131 /// for.
2132 ///
2133 /// \param TemplateLoc the location of the template name that started the
2134 /// template-id we are checking.
2135 ///
2136 /// \param RAngleLoc the location of the right angle bracket ('>') that
2137 /// terminates the template-id.
2138 ///
2139 /// \param Param the template template parameter whose default we are
2140 /// substituting into.
2141 ///
2142 /// \param Converted the list of template arguments provided for template
2143 /// parameters that precede \p Param in the template parameter list.
2144 ///
2145 /// \returns the substituted template argument, or NULL if an error occurred.
2146 static TemplateName
2147 SubstDefaultTemplateArgument(Sema &SemaRef,
2148                              TemplateDecl *Template,
2149                              SourceLocation TemplateLoc,
2150                              SourceLocation RAngleLoc,
2151                              TemplateTemplateParmDecl *Param,
2152                        llvm::SmallVectorImpl<TemplateArgument> &Converted) {
2153   TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2154                                     Converted.data(), Converted.size());
2155
2156   MultiLevelTemplateArgumentList AllTemplateArgs
2157     = SemaRef.getTemplateInstantiationArgs(Template, &TemplateArgs);
2158
2159   Sema::InstantiatingTemplate Inst(SemaRef, TemplateLoc,
2160                                    Template, Converted.data(),
2161                                    Converted.size(),
2162                                    SourceRange(TemplateLoc, RAngleLoc));
2163
2164   return SemaRef.SubstTemplateName(
2165                       Param->getDefaultArgument().getArgument().getAsTemplate(),
2166                               Param->getDefaultArgument().getTemplateNameLoc(),
2167                                    AllTemplateArgs);
2168 }
2169
2170 /// \brief If the given template parameter has a default template
2171 /// argument, substitute into that default template argument and
2172 /// return the corresponding template argument.
2173 TemplateArgumentLoc
2174 Sema::SubstDefaultTemplateArgumentIfAvailable(TemplateDecl *Template,
2175                                               SourceLocation TemplateLoc,
2176                                               SourceLocation RAngleLoc,
2177                                               Decl *Param,
2178                       llvm::SmallVectorImpl<TemplateArgument> &Converted) {
2179    if (TemplateTypeParmDecl *TypeParm = dyn_cast<TemplateTypeParmDecl>(Param)) {
2180     if (!TypeParm->hasDefaultArgument())
2181       return TemplateArgumentLoc();
2182
2183     TypeSourceInfo *DI = SubstDefaultTemplateArgument(*this, Template,
2184                                                       TemplateLoc,
2185                                                       RAngleLoc,
2186                                                       TypeParm,
2187                                                       Converted);
2188     if (DI)
2189       return TemplateArgumentLoc(TemplateArgument(DI->getType()), DI);
2190
2191     return TemplateArgumentLoc();
2192   }
2193
2194   if (NonTypeTemplateParmDecl *NonTypeParm
2195         = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2196     if (!NonTypeParm->hasDefaultArgument())
2197       return TemplateArgumentLoc();
2198
2199     ExprResult Arg = SubstDefaultTemplateArgument(*this, Template,
2200                                                         TemplateLoc,
2201                                                         RAngleLoc,
2202                                                         NonTypeParm,
2203                                                         Converted);
2204     if (Arg.isInvalid())
2205       return TemplateArgumentLoc();
2206
2207     Expr *ArgE = Arg.takeAs<Expr>();
2208     return TemplateArgumentLoc(TemplateArgument(ArgE), ArgE);
2209   }
2210
2211   TemplateTemplateParmDecl *TempTempParm
2212     = cast<TemplateTemplateParmDecl>(Param);
2213   if (!TempTempParm->hasDefaultArgument())
2214     return TemplateArgumentLoc();
2215
2216   TemplateName TName = SubstDefaultTemplateArgument(*this, Template,
2217                                                     TemplateLoc,
2218                                                     RAngleLoc,
2219                                                     TempTempParm,
2220                                                     Converted);
2221   if (TName.isNull())
2222     return TemplateArgumentLoc();
2223
2224   return TemplateArgumentLoc(TemplateArgument(TName),
2225                 TempTempParm->getDefaultArgument().getTemplateQualifierRange(),
2226                 TempTempParm->getDefaultArgument().getTemplateNameLoc());
2227 }
2228
2229 /// \brief Check that the given template argument corresponds to the given
2230 /// template parameter.
2231 ///
2232 /// \param Param The template parameter against which the argument will be
2233 /// checked.
2234 ///
2235 /// \param Arg The template argument.
2236 ///
2237 /// \param Template The template in which the template argument resides.
2238 ///
2239 /// \param TemplateLoc The location of the template name for the template
2240 /// whose argument list we're matching.
2241 ///
2242 /// \param RAngleLoc The location of the right angle bracket ('>') that closes
2243 /// the template argument list.
2244 ///
2245 /// \param ArgumentPackIndex The index into the argument pack where this
2246 /// argument will be placed. Only valid if the parameter is a parameter pack.
2247 ///
2248 /// \param Converted The checked, converted argument will be added to the
2249 /// end of this small vector.
2250 ///
2251 /// \param CTAK Describes how we arrived at this particular template argument:
2252 /// explicitly written, deduced, etc.
2253 ///
2254 /// \returns true on error, false otherwise.
2255 bool Sema::CheckTemplateArgument(NamedDecl *Param,
2256                                  const TemplateArgumentLoc &Arg,
2257                                  NamedDecl *Template,
2258                                  SourceLocation TemplateLoc,
2259                                  SourceLocation RAngleLoc,
2260                                  unsigned ArgumentPackIndex,
2261                             llvm::SmallVectorImpl<TemplateArgument> &Converted,
2262                                  CheckTemplateArgumentKind CTAK) {
2263   // Check template type parameters.
2264   if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param))
2265     return CheckTemplateTypeArgument(TTP, Arg, Converted);
2266
2267   // Check non-type template parameters.
2268   if (NonTypeTemplateParmDecl *NTTP =dyn_cast<NonTypeTemplateParmDecl>(Param)) {
2269     // Do substitution on the type of the non-type template parameter
2270     // with the template arguments we've seen thus far.  But if the
2271     // template has a dependent context then we cannot substitute yet.
2272     QualType NTTPType = NTTP->getType();
2273     if (NTTP->isParameterPack() && NTTP->isExpandedParameterPack())
2274       NTTPType = NTTP->getExpansionType(ArgumentPackIndex);
2275
2276     if (NTTPType->isDependentType() &&
2277         !isa<TemplateTemplateParmDecl>(Template) &&
2278         !Template->getDeclContext()->isDependentContext()) {
2279       // Do substitution on the type of the non-type template parameter.
2280       InstantiatingTemplate Inst(*this, TemplateLoc, Template,
2281                                  NTTP, Converted.data(), Converted.size(),
2282                                  SourceRange(TemplateLoc, RAngleLoc));
2283
2284       TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2285                                         Converted.data(), Converted.size());
2286       NTTPType = SubstType(NTTPType,
2287                            MultiLevelTemplateArgumentList(TemplateArgs),
2288                            NTTP->getLocation(),
2289                            NTTP->getDeclName());
2290       // If that worked, check the non-type template parameter type
2291       // for validity.
2292       if (!NTTPType.isNull())
2293         NTTPType = CheckNonTypeTemplateParameterType(NTTPType,
2294                                                      NTTP->getLocation());
2295       if (NTTPType.isNull())
2296         return true;
2297     }
2298
2299     switch (Arg.getArgument().getKind()) {
2300     case TemplateArgument::Null:
2301       assert(false && "Should never see a NULL template argument here");
2302       return true;
2303
2304     case TemplateArgument::Expression: {
2305       Expr *E = Arg.getArgument().getAsExpr();
2306       TemplateArgument Result;
2307       if (CheckTemplateArgument(NTTP, NTTPType, E, Result, CTAK))
2308         return true;
2309
2310       Converted.push_back(Result);
2311       break;
2312     }
2313
2314     case TemplateArgument::Declaration:
2315     case TemplateArgument::Integral:
2316       // We've already checked this template argument, so just copy
2317       // it to the list of converted arguments.
2318       Converted.push_back(Arg.getArgument());
2319       break;
2320
2321     case TemplateArgument::Template:
2322     case TemplateArgument::TemplateExpansion:
2323       // We were given a template template argument. It may not be ill-formed;
2324       // see below.
2325       if (DependentTemplateName *DTN
2326             = Arg.getArgument().getAsTemplateOrTemplatePattern()
2327                                               .getAsDependentTemplateName()) {
2328         // We have a template argument such as \c T::template X, which we
2329         // parsed as a template template argument. However, since we now
2330         // know that we need a non-type template argument, convert this
2331         // template name into an expression.
2332
2333         DeclarationNameInfo NameInfo(DTN->getIdentifier(),
2334                                      Arg.getTemplateNameLoc());
2335
2336         Expr *E = DependentScopeDeclRefExpr::Create(Context,
2337                                                     DTN->getQualifier(),
2338                                                Arg.getTemplateQualifierRange(),
2339                                                     NameInfo);
2340
2341         // If we parsed the template argument as a pack expansion, create a
2342         // pack expansion expression.
2343         if (Arg.getArgument().getKind() == TemplateArgument::TemplateExpansion){
2344           ExprResult Expansion = ActOnPackExpansion(E,
2345                                                   Arg.getTemplateEllipsisLoc());
2346           if (Expansion.isInvalid())
2347             return true;
2348
2349           E = Expansion.get();
2350         }
2351
2352         TemplateArgument Result;
2353         if (CheckTemplateArgument(NTTP, NTTPType, E, Result))
2354           return true;
2355
2356         Converted.push_back(Result);
2357         break;
2358       }
2359
2360       // We have a template argument that actually does refer to a class
2361       // template, template alias, or template template parameter, and
2362       // therefore cannot be a non-type template argument.
2363       Diag(Arg.getLocation(), diag::err_template_arg_must_be_expr)
2364         << Arg.getSourceRange();
2365
2366       Diag(Param->getLocation(), diag::note_template_param_here);
2367       return true;
2368
2369     case TemplateArgument::Type: {
2370       // We have a non-type template parameter but the template
2371       // argument is a type.
2372
2373       // C++ [temp.arg]p2:
2374       //   In a template-argument, an ambiguity between a type-id and
2375       //   an expression is resolved to a type-id, regardless of the
2376       //   form of the corresponding template-parameter.
2377       //
2378       // We warn specifically about this case, since it can be rather
2379       // confusing for users.
2380       QualType T = Arg.getArgument().getAsType();
2381       SourceRange SR = Arg.getSourceRange();
2382       if (T->isFunctionType())
2383         Diag(SR.getBegin(), diag::err_template_arg_nontype_ambig) << SR << T;
2384       else
2385         Diag(SR.getBegin(), diag::err_template_arg_must_be_expr) << SR;
2386       Diag(Param->getLocation(), diag::note_template_param_here);
2387       return true;
2388     }
2389
2390     case TemplateArgument::Pack:
2391       llvm_unreachable("Caller must expand template argument packs");
2392       break;
2393     }
2394
2395     return false;
2396   }
2397
2398
2399   // Check template template parameters.
2400   TemplateTemplateParmDecl *TempParm = cast<TemplateTemplateParmDecl>(Param);
2401
2402   // Substitute into the template parameter list of the template
2403   // template parameter, since previously-supplied template arguments
2404   // may appear within the template template parameter.
2405   {
2406     // Set up a template instantiation context.
2407     LocalInstantiationScope Scope(*this);
2408     InstantiatingTemplate Inst(*this, TemplateLoc, Template,
2409                                TempParm, Converted.data(), Converted.size(),
2410                                SourceRange(TemplateLoc, RAngleLoc));
2411
2412     TemplateArgumentList TemplateArgs(TemplateArgumentList::OnStack,
2413                                       Converted.data(), Converted.size());
2414     TempParm = cast_or_null<TemplateTemplateParmDecl>(
2415                       SubstDecl(TempParm, CurContext,
2416                                 MultiLevelTemplateArgumentList(TemplateArgs)));
2417     if (!TempParm)
2418       return true;
2419   }
2420
2421   switch (Arg.getArgument().getKind()) {
2422   case TemplateArgument::Null:
2423     assert(false && "Should never see a NULL template argument here");
2424     return true;
2425
2426   case TemplateArgument::Template:
2427   case TemplateArgument::TemplateExpansion:
2428     if (CheckTemplateArgument(TempParm, Arg))
2429       return true;
2430
2431     Converted.push_back(Arg.getArgument());
2432     break;
2433
2434   case TemplateArgument::Expression:
2435   case TemplateArgument::Type:
2436     // We have a template template parameter but the template
2437     // argument does not refer to a template.
2438     Diag(Arg.getLocation(), diag::err_template_arg_must_be_template);
2439     return true;
2440
2441   case TemplateArgument::Declaration:
2442     llvm_unreachable(
2443                        "Declaration argument with template template parameter");
2444     break;
2445   case TemplateArgument::Integral:
2446     llvm_unreachable(
2447                           "Integral argument with template template parameter");
2448     break;
2449
2450   case TemplateArgument::Pack:
2451     llvm_unreachable("Caller must expand template argument packs");
2452     break;
2453   }
2454
2455   return false;
2456 }
2457
2458 /// \brief Check that the given template argument list is well-formed
2459 /// for specializing the given template.
2460 bool Sema::CheckTemplateArgumentList(TemplateDecl *Template,
2461                                      SourceLocation TemplateLoc,
2462                                 const TemplateArgumentListInfo &TemplateArgs,
2463                                      bool PartialTemplateArgs,
2464                           llvm::SmallVectorImpl<TemplateArgument> &Converted) {
2465   TemplateParameterList *Params = Template->getTemplateParameters();
2466   unsigned NumParams = Params->size();
2467   unsigned NumArgs = TemplateArgs.size();
2468   bool Invalid = false;
2469
2470   SourceLocation RAngleLoc = TemplateArgs.getRAngleLoc();
2471
2472   bool HasParameterPack =
2473     NumParams > 0 && Params->getParam(NumParams - 1)->isTemplateParameterPack();
2474
2475   if ((NumArgs > NumParams && !HasParameterPack) ||
2476       (NumArgs < Params->getMinRequiredArguments() &&
2477        !PartialTemplateArgs)) {
2478     // FIXME: point at either the first arg beyond what we can handle,
2479     // or the '>', depending on whether we have too many or too few
2480     // arguments.
2481     SourceRange Range;
2482     if (NumArgs > NumParams)
2483       Range = SourceRange(TemplateArgs[NumParams].getLocation(), RAngleLoc);
2484     Diag(TemplateLoc, diag::err_template_arg_list_different_arity)
2485       << (NumArgs > NumParams)
2486       << (isa<ClassTemplateDecl>(Template)? 0 :
2487           isa<FunctionTemplateDecl>(Template)? 1 :
2488           isa<TemplateTemplateParmDecl>(Template)? 2 : 3)
2489       << Template << Range;
2490     Diag(Template->getLocation(), diag::note_template_decl_here)
2491       << Params->getSourceRange();
2492     Invalid = true;
2493   }
2494
2495   // C++ [temp.arg]p1:
2496   //   [...] The type and form of each template-argument specified in
2497   //   a template-id shall match the type and form specified for the
2498   //   corresponding parameter declared by the template in its
2499   //   template-parameter-list.
2500   llvm::SmallVector<TemplateArgument, 2> ArgumentPack;
2501   TemplateParameterList::iterator Param = Params->begin(),
2502                                ParamEnd = Params->end();
2503   unsigned ArgIdx = 0;
2504   LocalInstantiationScope InstScope(*this, true);
2505   while (Param != ParamEnd) {
2506     if (ArgIdx > NumArgs && PartialTemplateArgs)
2507       break;
2508
2509     if (ArgIdx < NumArgs) {
2510       // If we have an expanded parameter pack, make sure we don't have too
2511       // many arguments.
2512       if (NonTypeTemplateParmDecl *NTTP
2513                                 = dyn_cast<NonTypeTemplateParmDecl>(*Param)) {
2514         if (NTTP->isExpandedParameterPack() &&
2515             ArgumentPack.size() >= NTTP->getNumExpansionTypes()) {
2516           Diag(TemplateLoc, diag::err_template_arg_list_different_arity)
2517             << true
2518             << (isa<ClassTemplateDecl>(Template)? 0 :
2519                 isa<FunctionTemplateDecl>(Template)? 1 :
2520                 isa<TemplateTemplateParmDecl>(Template)? 2 : 3)
2521             << Template;
2522           Diag(Template->getLocation(), diag::note_template_decl_here)
2523             << Params->getSourceRange();
2524           return true;
2525         }
2526       }
2527
2528       // Check the template argument we were given.
2529       if (CheckTemplateArgument(*Param, TemplateArgs[ArgIdx], Template,
2530                                 TemplateLoc, RAngleLoc,
2531                                 ArgumentPack.size(), Converted))
2532         return true;
2533
2534       if ((*Param)->isTemplateParameterPack()) {
2535         // The template parameter was a template parameter pack, so take the
2536         // deduced argument and place it on the argument pack. Note that we
2537         // stay on the same template parameter so that we can deduce more
2538         // arguments.
2539         ArgumentPack.push_back(Converted.back());
2540         Converted.pop_back();
2541       } else {
2542         // Move to the next template parameter.
2543         ++Param;
2544       }
2545       ++ArgIdx;
2546       continue;
2547     }
2548
2549     // If we have a template parameter pack with no more corresponding
2550     // arguments, just break out now and we'll fill in the argument pack below.
2551     if ((*Param)->isTemplateParameterPack())
2552       break;
2553
2554     // We have a default template argument that we will use.
2555     TemplateArgumentLoc Arg;
2556
2557     // Retrieve the default template argument from the template
2558     // parameter. For each kind of template parameter, we substitute the
2559     // template arguments provided thus far and any "outer" template arguments
2560     // (when the template parameter was part of a nested template) into
2561     // the default argument.
2562     if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(*Param)) {
2563       if (!TTP->hasDefaultArgument()) {
2564         assert((Invalid || PartialTemplateArgs) && "Missing default argument");
2565         break;
2566       }
2567
2568       TypeSourceInfo *ArgType = SubstDefaultTemplateArgument(*this,
2569                                                              Template,
2570                                                              TemplateLoc,
2571                                                              RAngleLoc,
2572                                                              TTP,
2573                                                              Converted);
2574       if (!ArgType)
2575         return true;
2576
2577       Arg = TemplateArgumentLoc(TemplateArgument(ArgType->getType()),
2578                                 ArgType);
2579     } else if (NonTypeTemplateParmDecl *NTTP
2580                  = dyn_cast<NonTypeTemplateParmDecl>(*Param)) {
2581       if (!NTTP->hasDefaultArgument()) {
2582         assert((Invalid || PartialTemplateArgs) && "Missing default argument");
2583         break;
2584       }
2585
2586       ExprResult E = SubstDefaultTemplateArgument(*this, Template,
2587                                                               TemplateLoc,
2588                                                               RAngleLoc,
2589                                                               NTTP,
2590                                                               Converted);
2591       if (E.isInvalid())
2592         return true;
2593
2594       Expr *Ex = E.takeAs<Expr>();
2595       Arg = TemplateArgumentLoc(TemplateArgument(Ex), Ex);
2596     } else {
2597       TemplateTemplateParmDecl *TempParm
2598         = cast<TemplateTemplateParmDecl>(*Param);
2599
2600       if (!TempParm->hasDefaultArgument()) {
2601         assert((Invalid || PartialTemplateArgs) && "Missing default argument");
2602         break;
2603       }
2604
2605       TemplateName Name = SubstDefaultTemplateArgument(*this, Template,
2606                                                        TemplateLoc,
2607                                                        RAngleLoc,
2608                                                        TempParm,
2609                                                        Converted);
2610       if (Name.isNull())
2611         return true;
2612
2613       Arg = TemplateArgumentLoc(TemplateArgument(Name),
2614                   TempParm->getDefaultArgument().getTemplateQualifierRange(),
2615                   TempParm->getDefaultArgument().getTemplateNameLoc());
2616     }
2617
2618     // Introduce an instantiation record that describes where we are using
2619     // the default template argument.
2620     InstantiatingTemplate Instantiating(*this, RAngleLoc, Template, *Param,
2621                                         Converted.data(), Converted.size(),
2622                                         SourceRange(TemplateLoc, RAngleLoc));
2623
2624     // Check the default template argument.
2625     if (CheckTemplateArgument(*Param, Arg, Template, TemplateLoc,
2626                               RAngleLoc, 0, Converted))
2627       return true;
2628
2629     // Move to the next template parameter and argument.
2630     ++Param;
2631     ++ArgIdx;
2632   }
2633
2634   // Form argument packs for each of the parameter packs remaining.
2635   while (Param != ParamEnd) {
2636     // If we're checking a partial list of template arguments, don't fill
2637     // in arguments for non-template parameter packs.
2638
2639     if ((*Param)->isTemplateParameterPack()) {
2640       if (PartialTemplateArgs && ArgumentPack.empty()) {
2641         Converted.push_back(TemplateArgument());
2642       } else if (ArgumentPack.empty())
2643         Converted.push_back(TemplateArgument(0, 0));
2644       else {
2645         Converted.push_back(TemplateArgument::CreatePackCopy(Context,
2646                                                           ArgumentPack.data(),
2647                                                          ArgumentPack.size()));
2648         ArgumentPack.clear();
2649       }
2650     }
2651
2652     ++Param;
2653   }
2654
2655   return Invalid;
2656 }
2657
2658 namespace {
2659   class UnnamedLocalNoLinkageFinder
2660     : public TypeVisitor<UnnamedLocalNoLinkageFinder, bool>
2661   {
2662     Sema &S;
2663     SourceRange SR;
2664
2665     typedef TypeVisitor<UnnamedLocalNoLinkageFinder, bool> inherited;
2666
2667   public:
2668     UnnamedLocalNoLinkageFinder(Sema &S, SourceRange SR) : S(S), SR(SR) { }
2669
2670     bool Visit(QualType T) {
2671       return inherited::Visit(T.getTypePtr());
2672     }
2673
2674 #define TYPE(Class, Parent) \
2675     bool Visit##Class##Type(const Class##Type *);
2676 #define ABSTRACT_TYPE(Class, Parent) \
2677     bool Visit##Class##Type(const Class##Type *) { return false; }
2678 #define NON_CANONICAL_TYPE(Class, Parent) \
2679     bool Visit##Class##Type(const Class##Type *) { return false; }
2680 #include "clang/AST/TypeNodes.def"
2681
2682     bool VisitTagDecl(const TagDecl *Tag);
2683     bool VisitNestedNameSpecifier(NestedNameSpecifier *NNS);
2684   };
2685 }
2686
2687 bool UnnamedLocalNoLinkageFinder::VisitBuiltinType(const BuiltinType*) {
2688   return false;
2689 }
2690
2691 bool UnnamedLocalNoLinkageFinder::VisitComplexType(const ComplexType* T) {
2692   return Visit(T->getElementType());
2693 }
2694
2695 bool UnnamedLocalNoLinkageFinder::VisitPointerType(const PointerType* T) {
2696   return Visit(T->getPointeeType());
2697 }
2698
2699 bool UnnamedLocalNoLinkageFinder::VisitBlockPointerType(
2700                                                     const BlockPointerType* T) {
2701   return Visit(T->getPointeeType());
2702 }
2703
2704 bool UnnamedLocalNoLinkageFinder::VisitLValueReferenceType(
2705                                                 const LValueReferenceType* T) {
2706   return Visit(T->getPointeeType());
2707 }
2708
2709 bool UnnamedLocalNoLinkageFinder::VisitRValueReferenceType(
2710                                                 const RValueReferenceType* T) {
2711   return Visit(T->getPointeeType());
2712 }
2713
2714 bool UnnamedLocalNoLinkageFinder::VisitMemberPointerType(
2715                                                   const MemberPointerType* T) {
2716   return Visit(T->getPointeeType()) || Visit(QualType(T->getClass(), 0));
2717 }
2718
2719 bool UnnamedLocalNoLinkageFinder::VisitConstantArrayType(
2720                                                   const ConstantArrayType* T) {
2721   return Visit(T->getElementType());
2722 }
2723
2724 bool UnnamedLocalNoLinkageFinder::VisitIncompleteArrayType(
2725                                                  const IncompleteArrayType* T) {
2726   return Visit(T->getElementType());
2727 }
2728
2729 bool UnnamedLocalNoLinkageFinder::VisitVariableArrayType(
2730                                                    const VariableArrayType* T) {
2731   return Visit(T->getElementType());
2732 }
2733
2734 bool UnnamedLocalNoLinkageFinder::VisitDependentSizedArrayType(
2735                                             const DependentSizedArrayType* T) {
2736   return Visit(T->getElementType());
2737 }
2738
2739 bool UnnamedLocalNoLinkageFinder::VisitDependentSizedExtVectorType(
2740                                          const DependentSizedExtVectorType* T) {
2741   return Visit(T->getElementType());
2742 }
2743
2744 bool UnnamedLocalNoLinkageFinder::VisitVectorType(const VectorType* T) {
2745   return Visit(T->getElementType());
2746 }
2747
2748 bool UnnamedLocalNoLinkageFinder::VisitExtVectorType(const ExtVectorType* T) {
2749   return Visit(T->getElementType());
2750 }
2751
2752 bool UnnamedLocalNoLinkageFinder::VisitFunctionProtoType(
2753                                                   const FunctionProtoType* T) {
2754   for (FunctionProtoType::arg_type_iterator A = T->arg_type_begin(),
2755                                          AEnd = T->arg_type_end();
2756        A != AEnd; ++A) {
2757     if (Visit(*A))
2758       return true;
2759   }
2760
2761   return Visit(T->getResultType());
2762 }
2763
2764 bool UnnamedLocalNoLinkageFinder::VisitFunctionNoProtoType(
2765                                                const FunctionNoProtoType* T) {
2766   return Visit(T->getResultType());
2767 }
2768
2769 bool UnnamedLocalNoLinkageFinder::VisitUnresolvedUsingType(
2770                                                   const UnresolvedUsingType*) {
2771   return false;
2772 }
2773
2774 bool UnnamedLocalNoLinkageFinder::VisitTypeOfExprType(const TypeOfExprType*) {
2775   return false;
2776 }
2777
2778 bool UnnamedLocalNoLinkageFinder::VisitTypeOfType(const TypeOfType* T) {
2779   return Visit(T->getUnderlyingType());
2780 }
2781
2782 bool UnnamedLocalNoLinkageFinder::VisitDecltypeType(const DecltypeType*) {
2783   return false;
2784 }
2785
2786 bool UnnamedLocalNoLinkageFinder::VisitAutoType(const AutoType *T) {
2787   return Visit(T->getDeducedType());
2788 }
2789
2790 bool UnnamedLocalNoLinkageFinder::VisitRecordType(const RecordType* T) {
2791   return VisitTagDecl(T->getDecl());
2792 }
2793
2794 bool UnnamedLocalNoLinkageFinder::VisitEnumType(const EnumType* T) {
2795   return VisitTagDecl(T->getDecl());
2796 }
2797
2798 bool UnnamedLocalNoLinkageFinder::VisitTemplateTypeParmType(
2799                                                  const TemplateTypeParmType*) {
2800   return false;
2801 }
2802
2803 bool UnnamedLocalNoLinkageFinder::VisitSubstTemplateTypeParmPackType(
2804                                         const SubstTemplateTypeParmPackType *) {
2805   return false;
2806 }
2807
2808 bool UnnamedLocalNoLinkageFinder::VisitTemplateSpecializationType(
2809                                             const TemplateSpecializationType*) {
2810   return false;
2811 }
2812
2813 bool UnnamedLocalNoLinkageFinder::VisitInjectedClassNameType(
2814                                               const InjectedClassNameType* T) {
2815   return VisitTagDecl(T->getDecl());
2816 }
2817
2818 bool UnnamedLocalNoLinkageFinder::VisitDependentNameType(
2819                                                    const DependentNameType* T) {
2820   return VisitNestedNameSpecifier(T->getQualifier());
2821 }
2822
2823 bool UnnamedLocalNoLinkageFinder::VisitDependentTemplateSpecializationType(
2824                                  const DependentTemplateSpecializationType* T) {
2825   return VisitNestedNameSpecifier(T->getQualifier());
2826 }
2827
2828 bool UnnamedLocalNoLinkageFinder::VisitPackExpansionType(
2829                                                    const PackExpansionType* T) {
2830   return Visit(T->getPattern());
2831 }
2832
2833 bool UnnamedLocalNoLinkageFinder::VisitObjCObjectType(const ObjCObjectType *) {
2834   return false;
2835 }
2836
2837 bool UnnamedLocalNoLinkageFinder::VisitObjCInterfaceType(
2838                                                    const ObjCInterfaceType *) {
2839   return false;
2840 }
2841
2842 bool UnnamedLocalNoLinkageFinder::VisitObjCObjectPointerType(
2843                                                 const ObjCObjectPointerType *) {
2844   return false;
2845 }
2846
2847 bool UnnamedLocalNoLinkageFinder::VisitTagDecl(const TagDecl *Tag) {
2848   if (Tag->getDeclContext()->isFunctionOrMethod()) {
2849     S.Diag(SR.getBegin(), diag::ext_template_arg_local_type)
2850       << S.Context.getTypeDeclType(Tag) << SR;
2851     return true;
2852   }
2853
2854   if (!Tag->getDeclName() && !Tag->getTypedefForAnonDecl()) {
2855     S.Diag(SR.getBegin(), diag::ext_template_arg_unnamed_type) << SR;
2856     S.Diag(Tag->getLocation(), diag::note_template_unnamed_type_here);
2857     return true;
2858   }
2859
2860   return false;
2861 }
2862
2863 bool UnnamedLocalNoLinkageFinder::VisitNestedNameSpecifier(
2864                                                     NestedNameSpecifier *NNS) {
2865   if (NNS->getPrefix() && VisitNestedNameSpecifier(NNS->getPrefix()))
2866     return true;
2867
2868   switch (NNS->getKind()) {
2869   case NestedNameSpecifier::Identifier:
2870   case NestedNameSpecifier::Namespace:
2871   case NestedNameSpecifier::Global:
2872     return false;
2873
2874   case NestedNameSpecifier::TypeSpec:
2875   case NestedNameSpecifier::TypeSpecWithTemplate:
2876     return Visit(QualType(NNS->getAsType(), 0));
2877   }
2878   return false;
2879 }
2880
2881
2882 /// \brief Check a template argument against its corresponding
2883 /// template type parameter.
2884 ///
2885 /// This routine implements the semantics of C++ [temp.arg.type]. It
2886 /// returns true if an error occurred, and false otherwise.
2887 bool Sema::CheckTemplateArgument(TemplateTypeParmDecl *Param,
2888                                  TypeSourceInfo *ArgInfo) {
2889   assert(ArgInfo && "invalid TypeSourceInfo");
2890   QualType Arg = ArgInfo->getType();
2891   SourceRange SR = ArgInfo->getTypeLoc().getSourceRange();
2892
2893   if (Arg->isVariablyModifiedType()) {
2894     return Diag(SR.getBegin(), diag::err_variably_modified_template_arg) << Arg;
2895   } else if (Context.hasSameUnqualifiedType(Arg, Context.OverloadTy)) {
2896     return Diag(SR.getBegin(), diag::err_template_arg_overload_type) << SR;
2897   }
2898
2899   // C++03 [temp.arg.type]p2:
2900   //   A local type, a type with no linkage, an unnamed type or a type
2901   //   compounded from any of these types shall not be used as a
2902   //   template-argument for a template type-parameter.
2903   //
2904   // C++0x allows these, and even in C++03 we allow them as an extension with
2905   // a warning.
2906   if (!LangOpts.CPlusPlus0x && Arg->hasUnnamedOrLocalType()) {
2907     UnnamedLocalNoLinkageFinder Finder(*this, SR);
2908     (void)Finder.Visit(Context.getCanonicalType(Arg));
2909   }
2910
2911   return false;
2912 }
2913
2914 /// \brief Checks whether the given template argument is the address
2915 /// of an object or function according to C++ [temp.arg.nontype]p1.
2916 static bool
2917 CheckTemplateArgumentAddressOfObjectOrFunction(Sema &S,
2918                                                NonTypeTemplateParmDecl *Param,
2919                                                QualType ParamType,
2920                                                Expr *ArgIn,
2921                                                TemplateArgument &Converted) {
2922   bool Invalid = false;
2923   Expr *Arg = ArgIn;
2924   QualType ArgType = Arg->getType();
2925
2926   // See through any implicit casts we added to fix the type.
2927   while (ImplicitCastExpr *Cast = dyn_cast<ImplicitCastExpr>(Arg))
2928     Arg = Cast->getSubExpr();
2929
2930   // C++ [temp.arg.nontype]p1:
2931   //
2932   //   A template-argument for a non-type, non-template
2933   //   template-parameter shall be one of: [...]
2934   //
2935   //     -- the address of an object or function with external
2936   //        linkage, including function templates and function
2937   //        template-ids but excluding non-static class members,
2938   //        expressed as & id-expression where the & is optional if
2939   //        the name refers to a function or array, or if the
2940   //        corresponding template-parameter is a reference; or
2941   DeclRefExpr *DRE = 0;
2942
2943   // In C++98/03 mode, give an extension warning on any extra parentheses.
2944   // See http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#773
2945   bool ExtraParens = false;
2946   while (ParenExpr *Parens = dyn_cast<ParenExpr>(Arg)) {
2947     if (!Invalid && !ExtraParens && !S.getLangOptions().CPlusPlus0x) {
2948       S.Diag(Arg->getSourceRange().getBegin(),
2949              diag::ext_template_arg_extra_parens)
2950         << Arg->getSourceRange();
2951       ExtraParens = true;
2952     }
2953
2954     Arg = Parens->getSubExpr();
2955   }
2956
2957   bool AddressTaken = false;
2958   SourceLocation AddrOpLoc;
2959   if (UnaryOperator *UnOp = dyn_cast<UnaryOperator>(Arg)) {
2960     if (UnOp->getOpcode() == UO_AddrOf) {
2961       DRE = dyn_cast<DeclRefExpr>(UnOp->getSubExpr());
2962       AddressTaken = true;
2963       AddrOpLoc = UnOp->getOperatorLoc();
2964     }
2965   } else
2966     DRE = dyn_cast<DeclRefExpr>(Arg);
2967
2968   if (!DRE) {
2969     S.Diag(Arg->getLocStart(), diag::err_template_arg_not_decl_ref)
2970       << Arg->getSourceRange();
2971     S.Diag(Param->getLocation(), diag::note_template_param_here);
2972     return true;
2973   }
2974
2975   // Stop checking the precise nature of the argument if it is value dependent,
2976   // it should be checked when instantiated.
2977   if (Arg->isValueDependent()) {
2978     Converted = TemplateArgument(ArgIn);
2979     return false;
2980   }
2981
2982   if (!isa<ValueDecl>(DRE->getDecl())) {
2983     S.Diag(Arg->getSourceRange().getBegin(),
2984            diag::err_template_arg_not_object_or_func_form)
2985       << Arg->getSourceRange();
2986     S.Diag(Param->getLocation(), diag::note_template_param_here);
2987     return true;
2988   }
2989
2990   NamedDecl *Entity = 0;
2991
2992   // Cannot refer to non-static data members
2993   if (FieldDecl *Field = dyn_cast<FieldDecl>(DRE->getDecl())) {
2994     S.Diag(Arg->getSourceRange().getBegin(), diag::err_template_arg_field)
2995       << Field << Arg->getSourceRange();
2996     S.Diag(Param->getLocation(), diag::note_template_param_here);
2997     return true;
2998   }
2999
3000   // Cannot refer to non-static member functions
3001   if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(DRE->getDecl()))
3002     if (!Method->isStatic()) {
3003       S.Diag(Arg->getSourceRange().getBegin(), diag::err_template_arg_method)
3004         << Method << Arg->getSourceRange();
3005       S.Diag(Param->getLocation(), diag::note_template_param_here);
3006       return true;
3007     }
3008
3009   // Functions must have external linkage.
3010   if (FunctionDecl *Func = dyn_cast<FunctionDecl>(DRE->getDecl())) {
3011     if (!isExternalLinkage(Func->getLinkage())) {
3012       S.Diag(Arg->getSourceRange().getBegin(),
3013              diag::err_template_arg_function_not_extern)
3014         << Func << Arg->getSourceRange();
3015       S.Diag(Func->getLocation(), diag::note_template_arg_internal_object)
3016         << true;
3017       return true;
3018     }
3019
3020     // Okay: we've named a function with external linkage.
3021     Entity = Func;
3022
3023     // If the template parameter has pointer type, the function decays.
3024     if (ParamType->isPointerType() && !AddressTaken)
3025       ArgType = S.Context.getPointerType(Func->getType());
3026     else if (AddressTaken && ParamType->isReferenceType()) {
3027       // If we originally had an address-of operator, but the
3028       // parameter has reference type, complain and (if things look
3029       // like they will work) drop the address-of operator.
3030       if (!S.Context.hasSameUnqualifiedType(Func->getType(),
3031                                             ParamType.getNonReferenceType())) {
3032         S.Diag(AddrOpLoc, diag::err_template_arg_address_of_non_pointer)
3033           << ParamType;
3034         S.Diag(Param->getLocation(), diag::note_template_param_here);
3035         return true;
3036       }
3037
3038       S.Diag(AddrOpLoc, diag::err_template_arg_address_of_non_pointer)
3039         << ParamType
3040         << FixItHint::CreateRemoval(AddrOpLoc);
3041       S.Diag(Param->getLocation(), diag::note_template_param_here);
3042
3043       ArgType = Func->getType();
3044     }
3045   } else if (VarDecl *Var = dyn_cast<VarDecl>(DRE->getDecl())) {
3046     if (!isExternalLinkage(Var->getLinkage())) {
3047       S.Diag(Arg->getSourceRange().getBegin(),
3048              diag::err_template_arg_object_not_extern)
3049         << Var << Arg->getSourceRange();
3050       S.Diag(Var->getLocation(), diag::note_template_arg_internal_object)
3051         << true;
3052       return true;
3053     }
3054
3055     // A value of reference type is not an object.
3056     if (Var->getType()->isReferenceType()) {
3057       S.Diag(Arg->getSourceRange().getBegin(),
3058              diag::err_template_arg_reference_var)
3059         << Var->getType() << Arg->getSourceRange();
3060       S.Diag(Param->getLocation(), diag::note_template_param_here);
3061       return true;
3062     }
3063
3064     // Okay: we've named an object with external linkage
3065     Entity = Var;
3066
3067     // If the template parameter has pointer type, we must have taken
3068     // the address of this object.
3069     if (ParamType->isReferenceType()) {
3070       if (AddressTaken) {
3071         // If we originally had an address-of operator, but the
3072         // parameter has reference type, complain and (if things look
3073         // like they will work) drop the address-of operator.
3074         if (!S.Context.hasSameUnqualifiedType(Var->getType(),
3075                                             ParamType.getNonReferenceType())) {
3076           S.Diag(AddrOpLoc, diag::err_template_arg_address_of_non_pointer)
3077             << ParamType;
3078           S.Diag(Param->getLocation(), diag::note_template_param_here);
3079           return true;
3080         }
3081
3082         S.Diag(AddrOpLoc, diag::err_template_arg_address_of_non_pointer)
3083           << ParamType
3084           << FixItHint::CreateRemoval(AddrOpLoc);
3085         S.Diag(Param->getLocation(), diag::note_template_param_here);
3086
3087         ArgType = Var->getType();
3088       }
3089     } else if (!AddressTaken && ParamType->isPointerType()) {
3090       if (Var->getType()->isArrayType()) {
3091         // Array-to-pointer decay.
3092         ArgType = S.Context.getArrayDecayedType(Var->getType());
3093       } else {
3094         // If the template parameter has pointer type but the address of
3095         // this object was not taken, complain and (possibly) recover by
3096         // taking the address of the entity.
3097         ArgType = S.Context.getPointerType(Var->getType());
3098         if (!S.Context.hasSameUnqualifiedType(ArgType, ParamType)) {
3099           S.Diag(Arg->getLocStart(), diag::err_template_arg_not_address_of)
3100             << ParamType;
3101           S.Diag(Param->getLocation(), diag::note_template_param_here);
3102           return true;
3103         }
3104
3105         S.Diag(Arg->getLocStart(), diag::err_template_arg_not_address_of)
3106           << ParamType
3107           << FixItHint::CreateInsertion(Arg->getLocStart(), "&");
3108
3109         S.Diag(Param->getLocation(), diag::note_template_param_here);
3110       }
3111     }
3112   } else {
3113     // We found something else, but we don't know specifically what it is.
3114     S.Diag(Arg->getSourceRange().getBegin(),
3115            diag::err_template_arg_not_object_or_func)
3116       << Arg->getSourceRange();
3117     S.Diag(DRE->getDecl()->getLocation(), diag::note_template_arg_refers_here);
3118     return true;
3119   }
3120
3121   if (ParamType->isPointerType() &&
3122       !ParamType->getAs<PointerType>()->getPointeeType()->isFunctionType() &&
3123       S.IsQualificationConversion(ArgType, ParamType, false)) {
3124     // For pointer-to-object types, qualification conversions are
3125     // permitted.
3126   } else {
3127     if (const ReferenceType *ParamRef = ParamType->getAs<ReferenceType>()) {
3128       if (!ParamRef->getPointeeType()->isFunctionType()) {
3129         // C++ [temp.arg.nontype]p5b3:
3130         //   For a non-type template-parameter of type reference to
3131         //   object, no conversions apply. The type referred to by the
3132         //   reference may be more cv-qualified than the (otherwise
3133         //   identical) type of the template- argument. The
3134         //   template-parameter is bound directly to the
3135         //   template-argument, which shall be an lvalue.
3136
3137         // FIXME: Other qualifiers?
3138         unsigned ParamQuals = ParamRef->getPointeeType().getCVRQualifiers();
3139         unsigned ArgQuals = ArgType.getCVRQualifiers();
3140
3141         if ((ParamQuals | ArgQuals) != ParamQuals) {
3142           S.Diag(Arg->getSourceRange().getBegin(),
3143                  diag::err_template_arg_ref_bind_ignores_quals)
3144             << ParamType << Arg->getType()
3145             << Arg->getSourceRange();
3146           S.Diag(Param->getLocation(), diag::note_template_param_here);
3147           return true;
3148         }
3149       }
3150     }
3151
3152     // At this point, the template argument refers to an object or
3153     // function with external linkage. We now need to check whether the
3154     // argument and parameter types are compatible.
3155     if (!S.Context.hasSameUnqualifiedType(ArgType,
3156                                           ParamType.getNonReferenceType())) {
3157       // We can't perform this conversion or binding.
3158       if (ParamType->isReferenceType())
3159         S.Diag(Arg->getLocStart(), diag::err_template_arg_no_ref_bind)
3160           << ParamType << Arg->getType() << Arg->getSourceRange();
3161       else
3162         S.Diag(Arg->getLocStart(),  diag::err_template_arg_not_convertible)
3163           << Arg->getType() << ParamType << Arg->getSourceRange();
3164       S.Diag(Param->getLocation(), diag::note_template_param_here);
3165       return true;
3166     }
3167   }
3168
3169   // Create the template argument.
3170   Converted = TemplateArgument(Entity->getCanonicalDecl());
3171   S.MarkDeclarationReferenced(Arg->getLocStart(), Entity);
3172   return false;
3173 }
3174
3175 /// \brief Checks whether the given template argument is a pointer to
3176 /// member constant according to C++ [temp.arg.nontype]p1.
3177 bool Sema::CheckTemplateArgumentPointerToMember(Expr *Arg,
3178                                                 TemplateArgument &Converted) {
3179   bool Invalid = false;
3180
3181   // See through any implicit casts we added to fix the type.
3182   while (ImplicitCastExpr *Cast = dyn_cast<ImplicitCastExpr>(Arg))
3183     Arg = Cast->getSubExpr();
3184
3185   // C++ [temp.arg.nontype]p1:
3186   //
3187   //   A template-argument for a non-type, non-template
3188   //   template-parameter shall be one of: [...]
3189   //
3190   //     -- a pointer to member expressed as described in 5.3.1.
3191   DeclRefExpr *DRE = 0;
3192
3193   // In C++98/03 mode, give an extension warning on any extra parentheses.
3194   // See http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#773
3195   bool ExtraParens = false;
3196   while (ParenExpr *Parens = dyn_cast<ParenExpr>(Arg)) {
3197     if (!Invalid && !ExtraParens && !getLangOptions().CPlusPlus0x) {
3198       Diag(Arg->getSourceRange().getBegin(),
3199            diag::ext_template_arg_extra_parens)
3200         << Arg->getSourceRange();
3201       ExtraParens = true;
3202     }
3203
3204     Arg = Parens->getSubExpr();
3205   }
3206
3207   // A pointer-to-member constant written &Class::member.
3208   if (UnaryOperator *UnOp = dyn_cast<UnaryOperator>(Arg)) {
3209     if (UnOp->getOpcode() == UO_AddrOf) {
3210       DRE = dyn_cast<DeclRefExpr>(UnOp->getSubExpr());
3211       if (DRE && !DRE->getQualifier())
3212         DRE = 0;
3213     }
3214   }
3215   // A constant of pointer-to-member type.
3216   else if ((DRE = dyn_cast<DeclRefExpr>(Arg))) {
3217     if (ValueDecl *VD = dyn_cast<ValueDecl>(DRE->getDecl())) {
3218       if (VD->getType()->isMemberPointerType()) {
3219         if (isa<NonTypeTemplateParmDecl>(VD) ||
3220             (isa<VarDecl>(VD) &&
3221              Context.getCanonicalType(VD->getType()).isConstQualified())) {
3222           if (Arg->isTypeDependent() || Arg->isValueDependent())
3223             Converted = TemplateArgument(Arg);
3224           else
3225             Converted = TemplateArgument(VD->getCanonicalDecl());
3226           return Invalid;
3227         }
3228       }
3229     }
3230
3231     DRE = 0;
3232   }
3233
3234   if (!DRE)
3235     return Diag(Arg->getSourceRange().getBegin(),
3236                 diag::err_template_arg_not_pointer_to_member_form)
3237       << Arg->getSourceRange();
3238
3239   if (isa<FieldDecl>(DRE->getDecl()) || isa<CXXMethodDecl>(DRE->getDecl())) {
3240     assert((isa<FieldDecl>(DRE->getDecl()) ||
3241             !cast<CXXMethodDecl>(DRE->getDecl())->isStatic()) &&
3242            "Only non-static member pointers can make it here");
3243
3244     // Okay: this is the address of a non-static member, and therefore
3245     // a member pointer constant.
3246     if (Arg->isTypeDependent() || Arg->isValueDependent())
3247       Converted = TemplateArgument(Arg);
3248     else
3249       Converted = TemplateArgument(DRE->getDecl()->getCanonicalDecl());
3250     return Invalid;
3251   }
3252
3253   // We found something else, but we don't know specifically what it is.
3254   Diag(Arg->getSourceRange().getBegin(),
3255        diag::err_template_arg_not_pointer_to_member_form)
3256       << Arg->getSourceRange();
3257   Diag(DRE->getDecl()->getLocation(),
3258        diag::note_template_arg_refers_here);
3259   return true;
3260 }
3261
3262 /// \brief Check a template argument against its corresponding
3263 /// non-type template parameter.
3264 ///
3265 /// This routine implements the semantics of C++ [temp.arg.nontype].
3266 /// It returns true if an error occurred, and false otherwise. \p
3267 /// InstantiatedParamType is the type of the non-type template
3268 /// parameter after it has been instantiated.
3269 ///
3270 /// If no error was detected, Converted receives the converted template argument.
3271 bool Sema::CheckTemplateArgument(NonTypeTemplateParmDecl *Param,
3272                                  QualType InstantiatedParamType, Expr *&Arg,
3273                                  TemplateArgument &Converted,
3274                                  CheckTemplateArgumentKind CTAK) {
3275   SourceLocation StartLoc = Arg->getSourceRange().getBegin();
3276
3277   // If either the parameter has a dependent type or the argument is
3278   // type-dependent, there's nothing we can check now.
3279   if (InstantiatedParamType->isDependentType() || Arg->isTypeDependent()) {
3280     // FIXME: Produce a cloned, canonical expression?
3281     Converted = TemplateArgument(Arg);
3282     return false;
3283   }
3284
3285   // C++ [temp.arg.nontype]p5:
3286   //   The following conversions are performed on each expression used
3287   //   as a non-type template-argument. If a non-type
3288   //   template-argument cannot be converted to the type of the
3289   //   corresponding template-parameter then the program is
3290   //   ill-formed.
3291   //
3292   //     -- for a non-type template-parameter of integral or
3293   //        enumeration type, integral promotions (4.5) and integral
3294   //        conversions (4.7) are applied.
3295   QualType ParamType = InstantiatedParamType;
3296   QualType ArgType = Arg->getType();
3297   if (ParamType->isIntegralOrEnumerationType()) {
3298     // C++ [temp.arg.nontype]p1:
3299     //   A template-argument for a non-type, non-template
3300     //   template-parameter shall be one of:
3301     //
3302     //     -- an integral constant-expression of integral or enumeration
3303     //        type; or
3304     //     -- the name of a non-type template-parameter; or
3305     SourceLocation NonConstantLoc;
3306     llvm::APSInt Value;
3307     if (!ArgType->isIntegralOrEnumerationType()) {
3308       Diag(Arg->getSourceRange().getBegin(),
3309            diag::err_template_arg_not_integral_or_enumeral)
3310         << ArgType << Arg->getSourceRange();
3311       Diag(Param->getLocation(), diag::note_template_param_here);
3312       return true;
3313     } else if (!Arg->isValueDependent() &&
3314                !Arg->isIntegerConstantExpr(Value, Context, &NonConstantLoc)) {
3315       Diag(NonConstantLoc, diag::err_template_arg_not_ice)
3316         << ArgType << Arg->getSourceRange();
3317       return true;
3318     }
3319
3320     // From here on out, all we care about are the unqualified forms
3321     // of the parameter and argument types.
3322     ParamType = ParamType.getUnqualifiedType();
3323     ArgType = ArgType.getUnqualifiedType();
3324
3325     // Try to convert the argument to the parameter's type.
3326     if (Context.hasSameType(ParamType, ArgType)) {
3327       // Okay: no conversion necessary
3328     } else if (CTAK == CTAK_Deduced) {
3329       // C++ [temp.deduct.type]p17:
3330       //   If, in the declaration of a function template with a non-type
3331       //   template-parameter, the non-type template- parameter is used
3332       //   in an expression in the function parameter-list and, if the
3333       //   corresponding template-argument is deduced, the
3334       //   template-argument type shall match the type of the
3335       //   template-parameter exactly, except that a template-argument
3336       //   deduced from an array bound may be of any integral type.
3337       Diag(StartLoc, diag::err_deduced_non_type_template_arg_type_mismatch)
3338         << ArgType << ParamType;
3339       Diag(Param->getLocation(), diag::note_template_param_here);
3340       return true;
3341     } else if (ParamType->isBooleanType()) {
3342       // This is an integral-to-boolean conversion.
3343       ImpCastExprToType(Arg, ParamType, CK_IntegralToBoolean);
3344     } else if (IsIntegralPromotion(Arg, ArgType, ParamType) ||
3345                !ParamType->isEnumeralType()) {
3346       // This is an integral promotion or conversion.
3347       ImpCastExprToType(Arg, ParamType, CK_IntegralCast);
3348     } else {
3349       // We can't perform this conversion.
3350       Diag(Arg->getSourceRange().getBegin(),
3351            diag::err_template_arg_not_convertible)
3352         << Arg->getType() << InstantiatedParamType << Arg->getSourceRange();
3353       Diag(Param->getLocation(), diag::note_template_param_here);
3354       return true;
3355     }
3356
3357     QualType IntegerType = Context.getCanonicalType(ParamType);
3358     if (const EnumType *Enum = IntegerType->getAs<EnumType>())
3359       IntegerType = Context.getCanonicalType(Enum->getDecl()->getIntegerType());
3360
3361     if (!Arg->isValueDependent()) {
3362       llvm::APSInt OldValue = Value;
3363
3364       // Coerce the template argument's value to the value it will have
3365       // based on the template parameter's type.
3366       unsigned AllowedBits = Context.getTypeSize(IntegerType);
3367       if (Value.getBitWidth() != AllowedBits)
3368         Value = Value.extOrTrunc(AllowedBits);
3369       Value.setIsSigned(IntegerType->isSignedIntegerType());
3370
3371       // Complain if an unsigned parameter received a negative value.
3372       if (IntegerType->isUnsignedIntegerType()
3373           && (OldValue.isSigned() && OldValue.isNegative())) {
3374         Diag(Arg->getSourceRange().getBegin(), diag::warn_template_arg_negative)
3375           << OldValue.toString(10) << Value.toString(10) << Param->getType()
3376           << Arg->getSourceRange();
3377         Diag(Param->getLocation(), diag::note_template_param_here);
3378       }
3379
3380       // Complain if we overflowed the template parameter's type.
3381       unsigned RequiredBits;
3382       if (IntegerType->isUnsignedIntegerType())
3383         RequiredBits = OldValue.getActiveBits();
3384       else if (OldValue.isUnsigned())
3385         RequiredBits = OldValue.getActiveBits() + 1;
3386       else
3387         RequiredBits = OldValue.getMinSignedBits();
3388       if (RequiredBits > AllowedBits) {
3389         Diag(Arg->getSourceRange().getBegin(),
3390              diag::warn_template_arg_too_large)
3391           << OldValue.toString(10) << Value.toString(10) << Param->getType()
3392           << Arg->getSourceRange();
3393         Diag(Param->getLocation(), diag::note_template_param_here);
3394       }
3395     }
3396
3397     // Add the value of this argument to the list of converted
3398     // arguments. We use the bitwidth and signedness of the template
3399     // parameter.
3400     if (Arg->isValueDependent()) {
3401       // The argument is value-dependent. Create a new
3402       // TemplateArgument with the converted expression.
3403       Converted = TemplateArgument(Arg);
3404       return false;
3405     }
3406
3407     Converted = TemplateArgument(Value,
3408                                  ParamType->isEnumeralType() ? ParamType
3409                                                              : IntegerType);
3410     return false;
3411   }
3412
3413   DeclAccessPair FoundResult; // temporary for ResolveOverloadedFunction
3414
3415   // C++0x [temp.arg.nontype]p5 bullets 2, 4 and 6 permit conversion
3416   // from a template argument of type std::nullptr_t to a non-type
3417   // template parameter of type pointer to object, pointer to
3418   // function, or pointer-to-member, respectively.
3419   if (ArgType->isNullPtrType() &&
3420       (ParamType->isPointerType() || ParamType->isMemberPointerType())) {
3421     Converted = TemplateArgument((NamedDecl *)0);
3422     return false;
3423   }
3424
3425   // Handle pointer-to-function, reference-to-function, and
3426   // pointer-to-member-function all in (roughly) the same way.
3427   if (// -- For a non-type template-parameter of type pointer to
3428       //    function, only the function-to-pointer conversion (4.3) is
3429       //    applied. If the template-argument represents a set of
3430       //    overloaded functions (or a pointer to such), the matching
3431       //    function is selected from the set (13.4).
3432       (ParamType->isPointerType() &&
3433        ParamType->getAs<PointerType>()->getPointeeType()->isFunctionType()) ||
3434       // -- For a non-type template-parameter of type reference to
3435       //    function, no conversions apply. If the template-argument
3436       //    represents a set of overloaded functions, the matching
3437       //    function is selected from the set (13.4).
3438       (ParamType->isReferenceType() &&
3439        ParamType->getAs<ReferenceType>()->getPointeeType()->isFunctionType()) ||
3440       // -- For a non-type template-parameter of type pointer to
3441       //    member function, no conversions apply. If the
3442       //    template-argument represents a set of overloaded member
3443       //    functions, the matching member function is selected from
3444       //    the set (13.4).
3445       (ParamType->isMemberPointerType() &&
3446        ParamType->getAs<MemberPointerType>()->getPointeeType()
3447          ->isFunctionType())) {
3448
3449     if (Arg->getType() == Context.OverloadTy) {
3450       if (FunctionDecl *Fn = ResolveAddressOfOverloadedFunction(Arg, ParamType,
3451                                                                 true,
3452                                                                 FoundResult)) {
3453         if (DiagnoseUseOfDecl(Fn, Arg->getSourceRange().getBegin()))
3454           return true;
3455
3456         Arg = FixOverloadedFunctionReference(Arg, FoundResult, Fn);
3457         ArgType = Arg->getType();
3458       } else
3459         return true;
3460     }
3461
3462     if (!ParamType->isMemberPointerType())
3463       return CheckTemplateArgumentAddressOfObjectOrFunction(*this, Param,
3464                                                             ParamType,
3465                                                             Arg, Converted);
3466
3467     if (IsQualificationConversion(ArgType, ParamType.getNonReferenceType(),
3468                                   false)) {
3469       ImpCastExprToType(Arg, ParamType, CK_NoOp, CastCategory(Arg));
3470     } else if (!Context.hasSameUnqualifiedType(ArgType,
3471                                            ParamType.getNonReferenceType())) {
3472       // We can't perform this conversion.
3473       Diag(Arg->getSourceRange().getBegin(),
3474            diag::err_template_arg_not_convertible)
3475         << Arg->getType() << InstantiatedParamType << Arg->getSourceRange();
3476       Diag(Param->getLocation(), diag::note_template_param_here);
3477       return true;
3478     }
3479
3480     return CheckTemplateArgumentPointerToMember(Arg, Converted);
3481   }
3482
3483   if (ParamType->isPointerType()) {
3484     //   -- for a non-type template-parameter of type pointer to
3485     //      object, qualification conversions (4.4) and the
3486     //      array-to-pointer conversion (4.2) are applied.
3487     // C++0x also allows a value of std::nullptr_t.
3488     assert(ParamType->getPointeeType()->isIncompleteOrObjectType() &&
3489            "Only object pointers allowed here");
3490
3491     return CheckTemplateArgumentAddressOfObjectOrFunction(*this, Param,
3492                                                           ParamType,
3493                                                           Arg, Converted);
3494   }
3495
3496   if (const ReferenceType *ParamRefType = ParamType->getAs<ReferenceType>()) {
3497     //   -- For a non-type template-parameter of type reference to
3498     //      object, no conversions apply. The type referred to by the
3499     //      reference may be more cv-qualified than the (otherwise
3500     //      identical) type of the template-argument. The
3501     //      template-parameter is bound directly to the
3502     //      template-argument, which must be an lvalue.
3503     assert(ParamRefType->getPointeeType()->isIncompleteOrObjectType() &&
3504            "Only object references allowed here");
3505
3506     if (Arg->getType() == Context.OverloadTy) {
3507       if (FunctionDecl *Fn = ResolveAddressOfOverloadedFunction(Arg,
3508                                                  ParamRefType->getPointeeType(),
3509                                                                 true,
3510                                                                 FoundResult)) {
3511         if (DiagnoseUseOfDecl(Fn, Arg->getSourceRange().getBegin()))
3512           return true;
3513
3514         Arg = FixOverloadedFunctionReference(Arg, FoundResult, Fn);
3515         ArgType = Arg->getType();
3516       } else
3517         return true;
3518     }
3519
3520     return CheckTemplateArgumentAddressOfObjectOrFunction(*this, Param,
3521                                                           ParamType,
3522                                                           Arg, Converted);
3523   }
3524
3525   //     -- For a non-type template-parameter of type pointer to data
3526   //        member, qualification conversions (4.4) are applied.
3527   assert(ParamType->isMemberPointerType() && "Only pointers to members remain");
3528
3529   if (Context.hasSameUnqualifiedType(ParamType, ArgType)) {
3530     // Types match exactly: nothing more to do here.
3531   } else if (IsQualificationConversion(ArgType, ParamType, false)) {
3532     ImpCastExprToType(Arg, ParamType, CK_NoOp, CastCategory(Arg));
3533   } else {
3534     // We can't perform this conversion.
3535     Diag(Arg->getSourceRange().getBegin(),
3536          diag::err_template_arg_not_convertible)
3537       << Arg->getType() << InstantiatedParamType << Arg->getSourceRange();
3538     Diag(Param->getLocation(), diag::note_template_param_here);
3539     return true;
3540   }
3541
3542   return CheckTemplateArgumentPointerToMember(Arg, Converted);
3543 }
3544
3545 /// \brief Check a template argument against its corresponding
3546 /// template template parameter.
3547 ///
3548 /// This routine implements the semantics of C++ [temp.arg.template].
3549 /// It returns true if an error occurred, and false otherwise.
3550 bool Sema::CheckTemplateArgument(TemplateTemplateParmDecl *Param,
3551                                  const TemplateArgumentLoc &Arg) {
3552   TemplateName Name = Arg.getArgument().getAsTemplate();
3553   TemplateDecl *Template = Name.getAsTemplateDecl();
3554   if (!Template) {
3555     // Any dependent template name is fine.
3556     assert(Name.isDependent() && "Non-dependent template isn't a declaration?");
3557     return false;
3558   }
3559
3560   // C++ [temp.arg.template]p1:
3561   //   A template-argument for a template template-parameter shall be
3562   //   the name of a class template, expressed as id-expression. Only
3563   //   primary class templates are considered when matching the
3564   //   template template argument with the corresponding parameter;
3565   //   partial specializations are not considered even if their
3566   //   parameter lists match that of the template template parameter.
3567   //
3568   // Note that we also allow template template parameters here, which
3569   // will happen when we are dealing with, e.g., class template
3570   // partial specializations.
3571   if (!isa<ClassTemplateDecl>(Template) &&
3572       !isa<TemplateTemplateParmDecl>(Template)) {
3573     assert(isa<FunctionTemplateDecl>(Template) &&
3574            "Only function templates are possible here");
3575     Diag(Arg.getLocation(), diag::err_template_arg_not_class_template);
3576     Diag(Template->getLocation(), diag::note_template_arg_refers_here_func)
3577       << Template;
3578   }
3579
3580   return !TemplateParameterListsAreEqual(Template->getTemplateParameters(),
3581                                          Param->getTemplateParameters(),
3582                                          true,
3583                                          TPL_TemplateTemplateArgumentMatch,
3584                                          Arg.getLocation());
3585 }
3586
3587 /// \brief Given a non-type template argument that refers to a
3588 /// declaration and the type of its corresponding non-type template
3589 /// parameter, produce an expression that properly refers to that
3590 /// declaration.
3591 ExprResult
3592 Sema::BuildExpressionFromDeclTemplateArgument(const TemplateArgument &Arg,
3593                                               QualType ParamType,
3594                                               SourceLocation Loc) {
3595   assert(Arg.getKind() == TemplateArgument::Declaration &&
3596          "Only declaration template arguments permitted here");
3597   ValueDecl *VD = cast<ValueDecl>(Arg.getAsDecl());
3598
3599   if (VD->getDeclContext()->isRecord() &&
3600       (isa<CXXMethodDecl>(VD) || isa<FieldDecl>(VD))) {
3601     // If the value is a class member, we might have a pointer-to-member.
3602     // Determine whether the non-type template template parameter is of
3603     // pointer-to-member type. If so, we need to build an appropriate
3604     // expression for a pointer-to-member, since a "normal" DeclRefExpr
3605     // would refer to the member itself.
3606     if (ParamType->isMemberPointerType()) {
3607       QualType ClassType
3608         = Context.getTypeDeclType(cast<RecordDecl>(VD->getDeclContext()));
3609       NestedNameSpecifier *Qualifier
3610         = NestedNameSpecifier::Create(Context, 0, false,
3611                                       ClassType.getTypePtr());
3612       CXXScopeSpec SS;
3613       SS.setScopeRep(Qualifier);
3614
3615       // The actual value-ness of this is unimportant, but for
3616       // internal consistency's sake, references to instance methods
3617       // are r-values.
3618       ExprValueKind VK = VK_LValue;
3619       if (isa<CXXMethodDecl>(VD) && cast<CXXMethodDecl>(VD)->isInstance())
3620         VK = VK_RValue;
3621
3622       ExprResult RefExpr = BuildDeclRefExpr(VD,
3623                                             VD->getType().getNonReferenceType(),
3624                                             VK,
3625                                             Loc,
3626                                             &SS);
3627       if (RefExpr.isInvalid())
3628         return ExprError();
3629
3630       RefExpr = CreateBuiltinUnaryOp(Loc, UO_AddrOf, RefExpr.get());
3631
3632       // We might need to perform a trailing qualification conversion, since
3633       // the element type on the parameter could be more qualified than the
3634       // element type in the expression we constructed.
3635       if (IsQualificationConversion(((Expr*) RefExpr.get())->getType(),
3636                                     ParamType.getUnqualifiedType(), false)) {
3637         Expr *RefE = RefExpr.takeAs<Expr>();
3638         ImpCastExprToType(RefE, ParamType.getUnqualifiedType(), CK_NoOp);
3639         RefExpr = Owned(RefE);
3640       }
3641
3642       assert(!RefExpr.isInvalid() &&
3643              Context.hasSameType(((Expr*) RefExpr.get())->getType(),
3644                                  ParamType.getUnqualifiedType()));
3645       return move(RefExpr);
3646     }
3647   }
3648
3649   QualType T = VD->getType().getNonReferenceType();
3650   if (ParamType->isPointerType()) {
3651     // When the non-type template parameter is a pointer, take the
3652     // address of the declaration.
3653     ExprResult RefExpr = BuildDeclRefExpr(VD, T, VK_LValue, Loc);
3654     if (RefExpr.isInvalid())
3655       return ExprError();
3656
3657     if (T->isFunctionType() || T->isArrayType()) {
3658       // Decay functions and arrays.
3659       Expr *RefE = (Expr *)RefExpr.get();
3660       DefaultFunctionArrayConversion(RefE);
3661       if (RefE != RefExpr.get()) {
3662         RefExpr.release();
3663         RefExpr = Owned(RefE);
3664       }
3665
3666       return move(RefExpr);
3667     }
3668
3669     // Take the address of everything else
3670     return CreateBuiltinUnaryOp(Loc, UO_AddrOf, RefExpr.get());
3671   }
3672
3673   ExprValueKind VK = VK_RValue;
3674
3675   // If the non-type template parameter has reference type, qualify the
3676   // resulting declaration reference with the extra qualifiers on the
3677   // type that the reference refers to.
3678   if (const ReferenceType *TargetRef = ParamType->getAs<ReferenceType>()) {
3679     VK = VK_LValue;
3680     T = Context.getQualifiedType(T,
3681                               TargetRef->getPointeeType().getQualifiers());
3682   }
3683
3684   return BuildDeclRefExpr(VD, T, VK, Loc);
3685 }
3686
3687 /// \brief Construct a new expression that refers to the given
3688 /// integral template argument with the given source-location
3689 /// information.
3690 ///
3691 /// This routine takes care of the mapping from an integral template
3692 /// argument (which may have any integral type) to the appropriate
3693 /// literal value.
3694 ExprResult
3695 Sema::BuildExpressionFromIntegralTemplateArgument(const TemplateArgument &Arg,
3696                                                   SourceLocation Loc) {
3697   assert(Arg.getKind() == TemplateArgument::Integral &&
3698          "Operation is only valid for integral template arguments");
3699   QualType T = Arg.getIntegralType();
3700   if (T->isCharType() || T->isWideCharType())
3701     return Owned(new (Context) CharacterLiteral(
3702                                              Arg.getAsIntegral()->getZExtValue(),
3703                                              T->isWideCharType(),
3704                                              T,
3705                                              Loc));
3706   if (T->isBooleanType())
3707     return Owned(new (Context) CXXBoolLiteralExpr(
3708                                             Arg.getAsIntegral()->getBoolValue(),
3709                                             T,
3710                                             Loc));
3711
3712   QualType BT;
3713   if (const EnumType *ET = T->getAs<EnumType>())
3714     BT = ET->getDecl()->getPromotionType();
3715   else
3716     BT = T;
3717
3718   Expr *E = IntegerLiteral::Create(Context, *Arg.getAsIntegral(), BT, Loc);
3719   if (T->isEnumeralType()) {
3720     // FIXME: This is a hack. We need a better way to handle substituted
3721     // non-type template parameters.
3722     E = CStyleCastExpr::Create(Context, T, VK_RValue, CK_IntegralCast,
3723                                       E, 0,
3724                                       Context.getTrivialTypeSourceInfo(T, Loc),
3725                                       Loc, Loc);
3726   }
3727
3728   return Owned(E);
3729 }
3730
3731 /// \brief Match two template parameters within template parameter lists.
3732 static bool MatchTemplateParameterKind(Sema &S, NamedDecl *New, NamedDecl *Old,
3733                                        bool Complain,
3734                                      Sema::TemplateParameterListEqualKind Kind,
3735                                        SourceLocation TemplateArgLoc) {
3736   // Check the actual kind (type, non-type, template).
3737   if (Old->getKind() != New->getKind()) {
3738     if (Complain) {
3739       unsigned NextDiag = diag::err_template_param_different_kind;
3740       if (TemplateArgLoc.isValid()) {
3741         S.Diag(TemplateArgLoc, diag::err_template_arg_template_params_mismatch);
3742         NextDiag = diag::note_template_param_different_kind;
3743       }
3744       S.Diag(New->getLocation(), NextDiag)
3745         << (Kind != Sema::TPL_TemplateMatch);
3746       S.Diag(Old->getLocation(), diag::note_template_prev_declaration)
3747         << (Kind != Sema::TPL_TemplateMatch);
3748     }
3749
3750     return false;
3751   }
3752
3753   // Check that both are parameter packs are neither are parameter packs.
3754   // However, if we are matching a template template argument to a
3755   // template template parameter, the template template parameter can have
3756   // a parameter pack where the template template argument does not.
3757   if (Old->isTemplateParameterPack() != New->isTemplateParameterPack() &&
3758       !(Kind == Sema::TPL_TemplateTemplateArgumentMatch &&
3759         Old->isTemplateParameterPack())) {
3760     if (Complain) {
3761       unsigned NextDiag = diag::err_template_parameter_pack_non_pack;
3762       if (TemplateArgLoc.isValid()) {
3763         S.Diag(TemplateArgLoc,
3764              diag::err_template_arg_template_params_mismatch);
3765         NextDiag = diag::note_template_parameter_pack_non_pack;
3766       }
3767
3768       unsigned ParamKind = isa<TemplateTypeParmDecl>(New)? 0
3769                       : isa<NonTypeTemplateParmDecl>(New)? 1
3770                       : 2;
3771       S.Diag(New->getLocation(), NextDiag)
3772         << ParamKind << New->isParameterPack();
3773       S.Diag(Old->getLocation(), diag::note_template_parameter_pack_here)
3774         << ParamKind << Old->isParameterPack();
3775     }
3776
3777     return false;
3778   }
3779
3780   // For non-type template parameters, check the type of the parameter.
3781   if (NonTypeTemplateParmDecl *OldNTTP
3782                                     = dyn_cast<NonTypeTemplateParmDecl>(Old)) {
3783     NonTypeTemplateParmDecl *NewNTTP = cast<NonTypeTemplateParmDecl>(New);
3784
3785     // If we are matching a template template argument to a template
3786     // template parameter and one of the non-type template parameter types
3787     // is dependent, then we must wait until template instantiation time
3788     // to actually compare the arguments.
3789     if (Kind == Sema::TPL_TemplateTemplateArgumentMatch &&
3790         (OldNTTP->getType()->isDependentType() ||
3791          NewNTTP->getType()->isDependentType()))
3792       return true;
3793
3794     if (!S.Context.hasSameType(OldNTTP->getType(), NewNTTP->getType())) {
3795       if (Complain) {
3796         unsigned NextDiag = diag::err_template_nontype_parm_different_type;
3797         if (TemplateArgLoc.isValid()) {
3798           S.Diag(TemplateArgLoc,
3799                  diag::err_template_arg_template_params_mismatch);
3800           NextDiag = diag::note_template_nontype_parm_different_type;
3801         }
3802         S.Diag(NewNTTP->getLocation(), NextDiag)
3803           << NewNTTP->getType()
3804           << (Kind != Sema::TPL_TemplateMatch);
3805         S.Diag(OldNTTP->getLocation(),
3806                diag::note_template_nontype_parm_prev_declaration)
3807           << OldNTTP->getType();
3808       }
3809
3810       return false;
3811     }
3812
3813     return true;
3814   }
3815
3816   // For template template parameters, check the template parameter types.
3817   // The template parameter lists of template template
3818   // parameters must agree.
3819   if (TemplateTemplateParmDecl *OldTTP
3820                                     = dyn_cast<TemplateTemplateParmDecl>(Old)) {
3821     TemplateTemplateParmDecl *NewTTP = cast<TemplateTemplateParmDecl>(New);
3822     return S.TemplateParameterListsAreEqual(NewTTP->getTemplateParameters(),
3823                                             OldTTP->getTemplateParameters(),
3824                                             Complain,
3825                                         (Kind == Sema::TPL_TemplateMatch
3826                                            ? Sema::TPL_TemplateTemplateParmMatch
3827                                            : Kind),
3828                                             TemplateArgLoc);
3829   }
3830
3831   return true;
3832 }
3833
3834 /// \brief Diagnose a known arity mismatch when comparing template argument
3835 /// lists.
3836 static
3837 void DiagnoseTemplateParameterListArityMismatch(Sema &S,
3838                                                 TemplateParameterList *New,
3839                                                 TemplateParameterList *Old,
3840                                       Sema::TemplateParameterListEqualKind Kind,
3841                                                 SourceLocation TemplateArgLoc) {
3842   unsigned NextDiag = diag::err_template_param_list_different_arity;
3843   if (TemplateArgLoc.isValid()) {
3844     S.Diag(TemplateArgLoc, diag::err_template_arg_template_params_mismatch);
3845     NextDiag = diag::note_template_param_list_different_arity;
3846   }
3847   S.Diag(New->getTemplateLoc(), NextDiag)
3848     << (New->size() > Old->size())
3849     << (Kind != Sema::TPL_TemplateMatch)
3850     << SourceRange(New->getTemplateLoc(), New->getRAngleLoc());
3851   S.Diag(Old->getTemplateLoc(), diag::note_template_prev_declaration)
3852     << (Kind != Sema::TPL_TemplateMatch)
3853     << SourceRange(Old->getTemplateLoc(), Old->getRAngleLoc());
3854 }
3855
3856 /// \brief Determine whether the given template parameter lists are
3857 /// equivalent.
3858 ///
3859 /// \param New  The new template parameter list, typically written in the
3860 /// source code as part of a new template declaration.
3861 ///
3862 /// \param Old  The old template parameter list, typically found via
3863 /// name lookup of the template declared with this template parameter
3864 /// list.
3865 ///
3866 /// \param Complain  If true, this routine will produce a diagnostic if
3867 /// the template parameter lists are not equivalent.
3868 ///
3869 /// \param Kind describes how we are to match the template parameter lists.
3870 ///
3871 /// \param TemplateArgLoc If this source location is valid, then we
3872 /// are actually checking the template parameter list of a template
3873 /// argument (New) against the template parameter list of its
3874 /// corresponding template template parameter (Old). We produce
3875 /// slightly different diagnostics in this scenario.
3876 ///
3877 /// \returns True if the template parameter lists are equal, false
3878 /// otherwise.
3879 bool
3880 Sema::TemplateParameterListsAreEqual(TemplateParameterList *New,
3881                                      TemplateParameterList *Old,
3882                                      bool Complain,
3883                                      TemplateParameterListEqualKind Kind,
3884                                      SourceLocation TemplateArgLoc) {
3885   if (Old->size() != New->size() && Kind != TPL_TemplateTemplateArgumentMatch) {
3886     if (Complain)
3887       DiagnoseTemplateParameterListArityMismatch(*this, New, Old, Kind,
3888                                                  TemplateArgLoc);
3889
3890     return false;
3891   }
3892
3893   // C++0x [temp.arg.template]p3:
3894   //   A template-argument matches a template template-parameter (call it P)
3895   //   when each of the template parameters in the template-parameter-list of
3896   //   the template-argument's corresponding class template or template alias
3897   //   (call it A) matches the corresponding template parameter in the
3898   //   template-parameter-list of P. [...]
3899   TemplateParameterList::iterator NewParm = New->begin();
3900   TemplateParameterList::iterator NewParmEnd = New->end();
3901   for (TemplateParameterList::iterator OldParm = Old->begin(),
3902                                     OldParmEnd = Old->end();
3903        OldParm != OldParmEnd; ++OldParm) {
3904     if (Kind != TPL_TemplateTemplateArgumentMatch ||
3905         !(*OldParm)->isTemplateParameterPack()) {
3906       if (NewParm == NewParmEnd) {
3907         if (Complain)
3908           DiagnoseTemplateParameterListArityMismatch(*this, New, Old, Kind,
3909                                                      TemplateArgLoc);
3910
3911         return false;
3912       }
3913
3914       if (!MatchTemplateParameterKind(*this, *NewParm, *OldParm, Complain,
3915                                       Kind, TemplateArgLoc))
3916         return false;
3917
3918       ++NewParm;
3919       continue;
3920     }
3921
3922     // C++0x [temp.arg.template]p3:
3923     //   [...] When P's template- parameter-list contains a template parameter
3924     //   pack (14.5.3), the template parameter pack will match zero or more
3925     //   template parameters or template parameter packs in the
3926     //   template-parameter-list of A with the same type and form as the
3927     //   template parameter pack in P (ignoring whether those template
3928     //   parameters are template parameter packs).
3929     for (; NewParm != NewParmEnd; ++NewParm) {
3930       if (!MatchTemplateParameterKind(*this, *NewParm, *OldParm, Complain,
3931                                       Kind, TemplateArgLoc))
3932         return false;
3933     }
3934   }
3935
3936   // Make sure we exhausted all of the arguments.
3937   if (NewParm != NewParmEnd) {
3938     if (Complain)
3939       DiagnoseTemplateParameterListArityMismatch(*this, New, Old, Kind,
3940                                                  TemplateArgLoc);
3941
3942     return false;
3943   }
3944
3945   return true;
3946 }
3947
3948 /// \brief Check whether a template can be declared within this scope.
3949 ///
3950 /// If the template declaration is valid in this scope, returns
3951 /// false. Otherwise, issues a diagnostic and returns true.
3952 bool
3953 Sema::CheckTemplateDeclScope(Scope *S, TemplateParameterList *TemplateParams) {
3954   // Find the nearest enclosing declaration scope.
3955   while ((S->getFlags() & Scope::DeclScope) == 0 ||
3956          (S->getFlags() & Scope::TemplateParamScope) != 0)
3957     S = S->getParent();
3958
3959   // C++ [temp]p2:
3960   //   A template-declaration can appear only as a namespace scope or
3961   //   class scope declaration.
3962   DeclContext *Ctx = static_cast<DeclContext *>(S->getEntity());
3963   if (Ctx && isa<LinkageSpecDecl>(Ctx) &&
3964       cast<LinkageSpecDecl>(Ctx)->getLanguage() != LinkageSpecDecl::lang_cxx)
3965     return Diag(TemplateParams->getTemplateLoc(), diag::err_template_linkage)
3966              << TemplateParams->getSourceRange();
3967
3968   while (Ctx && isa<LinkageSpecDecl>(Ctx))
3969     Ctx = Ctx->getParent();
3970
3971   if (Ctx && (Ctx->isFileContext() || Ctx->isRecord()))
3972     return false;
3973
3974   return Diag(TemplateParams->getTemplateLoc(),
3975               diag::err_template_outside_namespace_or_class_scope)
3976     << TemplateParams->getSourceRange();
3977 }
3978
3979 /// \brief Determine what kind of template specialization the given declaration
3980 /// is.
3981 static TemplateSpecializationKind getTemplateSpecializationKind(NamedDecl *D) {
3982   if (!D)
3983     return TSK_Undeclared;
3984
3985   if (CXXRecordDecl *Record = dyn_cast<CXXRecordDecl>(D))
3986     return Record->getTemplateSpecializationKind();
3987   if (FunctionDecl *Function = dyn_cast<FunctionDecl>(D))
3988     return Function->getTemplateSpecializationKind();
3989   if (VarDecl *Var = dyn_cast<VarDecl>(D))
3990     return Var->getTemplateSpecializationKind();
3991
3992   return TSK_Undeclared;
3993 }
3994
3995 /// \brief Check whether a specialization is well-formed in the current
3996 /// context.
3997 ///
3998 /// This routine determines whether a template specialization can be declared
3999 /// in the current context (C++ [temp.expl.spec]p2).
4000 ///
4001 /// \param S the semantic analysis object for which this check is being
4002 /// performed.
4003 ///
4004 /// \param Specialized the entity being specialized or instantiated, which
4005 /// may be a kind of template (class template, function template, etc.) or
4006 /// a member of a class template (member function, static data member,
4007 /// member class).
4008 ///
4009 /// \param PrevDecl the previous declaration of this entity, if any.
4010 ///
4011 /// \param Loc the location of the explicit specialization or instantiation of
4012 /// this entity.
4013 ///
4014 /// \param IsPartialSpecialization whether this is a partial specialization of
4015 /// a class template.
4016 ///
4017 /// \returns true if there was an error that we cannot recover from, false
4018 /// otherwise.
4019 static bool CheckTemplateSpecializationScope(Sema &S,
4020                                              NamedDecl *Specialized,
4021                                              NamedDecl *PrevDecl,
4022                                              SourceLocation Loc,
4023                                              bool IsPartialSpecialization) {
4024   // Keep these "kind" numbers in sync with the %select statements in the
4025   // various diagnostics emitted by this routine.
4026   int EntityKind = 0;
4027   if (isa<ClassTemplateDecl>(Specialized))
4028     EntityKind = IsPartialSpecialization? 1 : 0;
4029   else if (isa<FunctionTemplateDecl>(Specialized))
4030     EntityKind = 2;
4031   else if (isa<CXXMethodDecl>(Specialized))
4032     EntityKind = 3;
4033   else if (isa<VarDecl>(Specialized))
4034     EntityKind = 4;
4035   else if (isa<RecordDecl>(Specialized))
4036     EntityKind = 5;
4037   else {
4038     S.Diag(Loc, diag::err_template_spec_unknown_kind);
4039     S.Diag(Specialized->getLocation(), diag::note_specialized_entity);
4040     return true;
4041   }
4042
4043   // C++ [temp.expl.spec]p2:
4044   //   An explicit specialization shall be declared in the namespace
4045   //   of which the template is a member, or, for member templates, in
4046   //   the namespace of which the enclosing class or enclosing class
4047   //   template is a member. An explicit specialization of a member
4048   //   function, member class or static data member of a class
4049   //   template shall be declared in the namespace of which the class
4050   //   template is a member. Such a declaration may also be a
4051   //   definition. If the declaration is not a definition, the
4052   //   specialization may be defined later in the name- space in which
4053   //   the explicit specialization was declared, or in a namespace
4054   //   that encloses the one in which the explicit specialization was
4055   //   declared.
4056   if (S.CurContext->getRedeclContext()->isFunctionOrMethod()) {
4057     S.Diag(Loc, diag::err_template_spec_decl_function_scope)
4058       << Specialized;
4059     return true;
4060   }
4061
4062   if (S.CurContext->isRecord() && !IsPartialSpecialization) {
4063     S.Diag(Loc, diag::err_template_spec_decl_class_scope)
4064       << Specialized;
4065     return true;
4066   }
4067
4068   // C++ [temp.class.spec]p6:
4069   //   A class template partial specialization may be declared or redeclared
4070   //   in any namespace scope in which its definition may be defined (14.5.1
4071   //   and 14.5.2).
4072   bool ComplainedAboutScope = false;
4073   DeclContext *SpecializedContext
4074     = Specialized->getDeclContext()->getEnclosingNamespaceContext();
4075   DeclContext *DC = S.CurContext->getEnclosingNamespaceContext();
4076   if ((!PrevDecl ||
4077        getTemplateSpecializationKind(PrevDecl) == TSK_Undeclared ||
4078        getTemplateSpecializationKind(PrevDecl) == TSK_ImplicitInstantiation)){
4079     // C++ [temp.exp.spec]p2:
4080     //   An explicit specialization shall be declared in the namespace of which
4081     //   the template is a member, or, for member templates, in the namespace
4082     //   of which the enclosing class or enclosing class template is a member.
4083     //   An explicit specialization of a member function, member class or
4084     //   static data member of a class template shall be declared in the
4085     //   namespace of which the class template is a member.
4086     //
4087     // C++0x [temp.expl.spec]p2:
4088     //   An explicit specialization shall be declared in a namespace enclosing
4089     //   the specialized template.
4090     if (!DC->InEnclosingNamespaceSetOf(SpecializedContext) &&
4091         !(S.getLangOptions().CPlusPlus0x && DC->Encloses(SpecializedContext))) {
4092       bool IsCPlusPlus0xExtension
4093         = !S.getLangOptions().CPlusPlus0x && DC->Encloses(SpecializedContext);
4094       if (isa<TranslationUnitDecl>(SpecializedContext))
4095         S.Diag(Loc, IsCPlusPlus0xExtension
4096                       ? diag::ext_template_spec_decl_out_of_scope_global
4097                       : diag::err_template_spec_decl_out_of_scope_global)
4098           << EntityKind << Specialized;
4099       else if (isa<NamespaceDecl>(SpecializedContext))
4100         S.Diag(Loc, IsCPlusPlus0xExtension
4101                       ? diag::ext_template_spec_decl_out_of_scope
4102                       : diag::err_template_spec_decl_out_of_scope)
4103           << EntityKind << Specialized
4104           << cast<NamedDecl>(SpecializedContext);
4105
4106       S.Diag(Specialized->getLocation(), diag::note_specialized_entity);
4107       ComplainedAboutScope = true;
4108     }
4109   }
4110
4111   // Make sure that this redeclaration (or definition) occurs in an enclosing
4112   // namespace.
4113   // Note that HandleDeclarator() performs this check for explicit
4114   // specializations of function templates, static data members, and member
4115   // functions, so we skip the check here for those kinds of entities.
4116   // FIXME: HandleDeclarator's diagnostics aren't quite as good, though.
4117   // Should we refactor that check, so that it occurs later?
4118   if (!ComplainedAboutScope && !DC->Encloses(SpecializedContext) &&
4119       !(isa<FunctionTemplateDecl>(Specialized) || isa<VarDecl>(Specialized) ||
4120         isa<FunctionDecl>(Specialized))) {
4121     if (isa<TranslationUnitDecl>(SpecializedContext))
4122       S.Diag(Loc, diag::err_template_spec_redecl_global_scope)
4123         << EntityKind << Specialized;
4124     else if (isa<NamespaceDecl>(SpecializedContext))
4125       S.Diag(Loc, diag::err_template_spec_redecl_out_of_scope)
4126         << EntityKind << Specialized
4127         << cast<NamedDecl>(SpecializedContext);
4128
4129     S.Diag(Specialized->getLocation(), diag::note_specialized_entity);
4130   }
4131
4132   // FIXME: check for specialization-after-instantiation errors and such.
4133
4134   return false;
4135 }
4136
4137 /// \brief Subroutine of Sema::CheckClassTemplatePartialSpecializationArgs
4138 /// that checks non-type template partial specialization arguments.
4139 static bool CheckNonTypeClassTemplatePartialSpecializationArgs(Sema &S,
4140                                                 NonTypeTemplateParmDecl *Param,
4141                                                   const TemplateArgument *Args,
4142                                                         unsigned NumArgs) {
4143   for (unsigned I = 0; I != NumArgs; ++I) {
4144     if (Args[I].getKind() == TemplateArgument::Pack) {
4145       if (CheckNonTypeClassTemplatePartialSpecializationArgs(S, Param,
4146                                                            Args[I].pack_begin(),
4147                                                            Args[I].pack_size()))
4148         return true;
4149
4150       continue;
4151     }
4152
4153     Expr *ArgExpr = Args[I].getAsExpr();
4154     if (!ArgExpr) {
4155       continue;
4156     }
4157
4158     // We can have a pack expansion of any of the bullets below.
4159     if (PackExpansionExpr *Expansion = dyn_cast<PackExpansionExpr>(ArgExpr))
4160       ArgExpr = Expansion->getPattern();
4161
4162     // Strip off any implicit casts we added as part of type checking.
4163     while (ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(ArgExpr))
4164       ArgExpr = ICE->getSubExpr();
4165
4166     // C++ [temp.class.spec]p8:
4167     //   A non-type argument is non-specialized if it is the name of a
4168     //   non-type parameter. All other non-type arguments are
4169     //   specialized.
4170     //
4171     // Below, we check the two conditions that only apply to
4172     // specialized non-type arguments, so skip any non-specialized
4173     // arguments.
4174     if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(ArgExpr))
4175       if (isa<NonTypeTemplateParmDecl>(DRE->getDecl()))
4176         continue;
4177
4178     // C++ [temp.class.spec]p9:
4179     //   Within the argument list of a class template partial
4180     //   specialization, the following restrictions apply:
4181     //     -- A partially specialized non-type argument expression
4182     //        shall not involve a template parameter of the partial
4183     //        specialization except when the argument expression is a
4184     //        simple identifier.
4185     if (ArgExpr->isTypeDependent() || ArgExpr->isValueDependent()) {
4186       S.Diag(ArgExpr->getLocStart(),
4187            diag::err_dependent_non_type_arg_in_partial_spec)
4188         << ArgExpr->getSourceRange();
4189       return true;
4190     }
4191
4192     //     -- The type of a template parameter corresponding to a
4193     //        specialized non-type argument shall not be dependent on a
4194     //        parameter of the specialization.
4195     if (Param->getType()->isDependentType()) {
4196       S.Diag(ArgExpr->getLocStart(),
4197            diag::err_dependent_typed_non_type_arg_in_partial_spec)
4198         << Param->getType()
4199         << ArgExpr->getSourceRange();
4200       S.Diag(Param->getLocation(), diag::note_template_param_here);
4201       return true;
4202     }
4203   }
4204
4205   return false;
4206 }
4207
4208 /// \brief Check the non-type template arguments of a class template
4209 /// partial specialization according to C++ [temp.class.spec]p9.
4210 ///
4211 /// \param TemplateParams the template parameters of the primary class
4212 /// template.
4213 ///
4214 /// \param TemplateArg the template arguments of the class template
4215 /// partial specialization.
4216 ///
4217 /// \returns true if there was an error, false otherwise.
4218 static bool CheckClassTemplatePartialSpecializationArgs(Sema &S,
4219                                         TemplateParameterList *TemplateParams,
4220                        llvm::SmallVectorImpl<TemplateArgument> &TemplateArgs) {
4221   const TemplateArgument *ArgList = TemplateArgs.data();
4222
4223   for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
4224     NonTypeTemplateParmDecl *Param
4225       = dyn_cast<NonTypeTemplateParmDecl>(TemplateParams->getParam(I));
4226     if (!Param)
4227       continue;
4228
4229     if (CheckNonTypeClassTemplatePartialSpecializationArgs(S, Param,
4230                                                            &ArgList[I], 1))
4231       return true;
4232   }
4233
4234   return false;
4235 }
4236
4237 /// \brief Retrieve the previous declaration of the given declaration.
4238 static NamedDecl *getPreviousDecl(NamedDecl *ND) {
4239   if (VarDecl *VD = dyn_cast<VarDecl>(ND))
4240     return VD->getPreviousDeclaration();
4241   if (FunctionDecl *FD = dyn_cast<FunctionDecl>(ND))
4242     return FD->getPreviousDeclaration();
4243   if (TagDecl *TD = dyn_cast<TagDecl>(ND))
4244     return TD->getPreviousDeclaration();
4245   if (TypedefDecl *TD = dyn_cast<TypedefDecl>(ND))
4246     return TD->getPreviousDeclaration();
4247   if (FunctionTemplateDecl *FTD = dyn_cast<FunctionTemplateDecl>(ND))
4248     return FTD->getPreviousDeclaration();
4249   if (ClassTemplateDecl *CTD = dyn_cast<ClassTemplateDecl>(ND))
4250     return CTD->getPreviousDeclaration();
4251   return 0;
4252 }
4253
4254 DeclResult
4255 Sema::ActOnClassTemplateSpecialization(Scope *S, unsigned TagSpec,
4256                                        TagUseKind TUK,
4257                                        SourceLocation KWLoc,
4258                                        CXXScopeSpec &SS,
4259                                        TemplateTy TemplateD,
4260                                        SourceLocation TemplateNameLoc,
4261                                        SourceLocation LAngleLoc,
4262                                        ASTTemplateArgsPtr TemplateArgsIn,
4263                                        SourceLocation RAngleLoc,
4264                                        AttributeList *Attr,
4265                                MultiTemplateParamsArg TemplateParameterLists) {
4266   assert(TUK != TUK_Reference && "References are not specializations");
4267
4268   // Find the class template we're specializing
4269   TemplateName Name = TemplateD.getAsVal<TemplateName>();
4270   ClassTemplateDecl *ClassTemplate
4271     = dyn_cast_or_null<ClassTemplateDecl>(Name.getAsTemplateDecl());
4272
4273   if (!ClassTemplate) {
4274     Diag(TemplateNameLoc, diag::err_not_class_template_specialization)
4275       << (Name.getAsTemplateDecl() &&
4276           isa<TemplateTemplateParmDecl>(Name.getAsTemplateDecl()));
4277     return true;
4278   }
4279
4280   bool isExplicitSpecialization = false;
4281   bool isPartialSpecialization = false;
4282
4283   // Check the validity of the template headers that introduce this
4284   // template.
4285   // FIXME: We probably shouldn't complain about these headers for
4286   // friend declarations.
4287   bool Invalid = false;
4288   TemplateParameterList *TemplateParams
4289     = MatchTemplateParametersToScopeSpecifier(TemplateNameLoc, SS,
4290                         (TemplateParameterList**)TemplateParameterLists.get(),
4291                                               TemplateParameterLists.size(),
4292                                               TUK == TUK_Friend,
4293                                               isExplicitSpecialization,
4294                                               Invalid);
4295   if (Invalid)
4296     return true;
4297
4298   unsigned NumMatchedTemplateParamLists = TemplateParameterLists.size();
4299   if (TemplateParams)
4300     --NumMatchedTemplateParamLists;
4301
4302   if (TemplateParams && TemplateParams->size() > 0) {
4303     isPartialSpecialization = true;
4304
4305     if (TUK == TUK_Friend) {
4306       Diag(KWLoc, diag::err_partial_specialization_friend)
4307         << SourceRange(LAngleLoc, RAngleLoc);
4308       return true;
4309     }
4310
4311     // C++ [temp.class.spec]p10:
4312     //   The template parameter list of a specialization shall not
4313     //   contain default template argument values.
4314     for (unsigned I = 0, N = TemplateParams->size(); I != N; ++I) {
4315       Decl *Param = TemplateParams->getParam(I);
4316       if (TemplateTypeParmDecl *TTP = dyn_cast<TemplateTypeParmDecl>(Param)) {
4317         if (TTP->hasDefaultArgument()) {
4318           Diag(TTP->getDefaultArgumentLoc(),
4319                diag::err_default_arg_in_partial_spec);
4320           TTP->removeDefaultArgument();
4321         }
4322       } else if (NonTypeTemplateParmDecl *NTTP
4323                    = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
4324         if (Expr *DefArg = NTTP->getDefaultArgument()) {
4325           Diag(NTTP->getDefaultArgumentLoc(),
4326                diag::err_default_arg_in_partial_spec)
4327             << DefArg->getSourceRange();
4328           NTTP->removeDefaultArgument();
4329         }
4330       } else {
4331         TemplateTemplateParmDecl *TTP = cast<TemplateTemplateParmDecl>(Param);
4332         if (TTP->hasDefaultArgument()) {
4333           Diag(TTP->getDefaultArgument().getLocation(),
4334                diag::err_default_arg_in_partial_spec)
4335             << TTP->getDefaultArgument().getSourceRange();
4336           TTP->removeDefaultArgument();
4337         }
4338       }
4339     }
4340   } else if (TemplateParams) {
4341     if (TUK == TUK_Friend)
4342       Diag(KWLoc, diag::err_template_spec_friend)
4343         << FixItHint::CreateRemoval(
4344                                 SourceRange(TemplateParams->getTemplateLoc(),
4345                                             TemplateParams->getRAngleLoc()))
4346         << SourceRange(LAngleLoc, RAngleLoc);
4347     else
4348       isExplicitSpecialization = true;
4349   } else if (TUK != TUK_Friend) {
4350     Diag(KWLoc, diag::err_template_spec_needs_header)
4351       << FixItHint::CreateInsertion(KWLoc, "template<> ");
4352     isExplicitSpecialization = true;
4353   }
4354
4355   // Check that the specialization uses the same tag kind as the
4356   // original template.
4357   TagTypeKind Kind = TypeWithKeyword::getTagTypeKindForTypeSpec(TagSpec);
4358   assert(Kind != TTK_Enum && "Invalid enum tag in class template spec!");
4359   if (!isAcceptableTagRedeclaration(ClassTemplate->getTemplatedDecl(),
4360                                     Kind, KWLoc,
4361                                     *ClassTemplate->getIdentifier())) {
4362     Diag(KWLoc, diag::err_use_with_wrong_tag)
4363       << ClassTemplate
4364       << FixItHint::CreateReplacement(KWLoc,
4365                             ClassTemplate->getTemplatedDecl()->getKindName());
4366     Diag(ClassTemplate->getTemplatedDecl()->getLocation(),
4367          diag::note_previous_use);
4368     Kind = ClassTemplate->getTemplatedDecl()->getTagKind();
4369   }
4370
4371   // Translate the parser's template argument list in our AST format.
4372   TemplateArgumentListInfo TemplateArgs;
4373   TemplateArgs.setLAngleLoc(LAngleLoc);
4374   TemplateArgs.setRAngleLoc(RAngleLoc);
4375   translateTemplateArguments(TemplateArgsIn, TemplateArgs);
4376
4377   // Check for unexpanded parameter packs in any of the template arguments.
4378   for (unsigned I = 0, N = TemplateArgs.size(); I != N; ++I)
4379     if (DiagnoseUnexpandedParameterPack(TemplateArgs[I],
4380                                         UPPC_PartialSpecialization))
4381       return true;
4382
4383   // Check that the template argument list is well-formed for this
4384   // template.
4385   llvm::SmallVector<TemplateArgument, 4> Converted;
4386   if (CheckTemplateArgumentList(ClassTemplate, TemplateNameLoc,
4387                                 TemplateArgs, false, Converted))
4388     return true;
4389
4390   assert((Converted.size() == ClassTemplate->getTemplateParameters()->size()) &&
4391          "Converted template argument list is too short!");
4392
4393   // Find the class template (partial) specialization declaration that
4394   // corresponds to these arguments.
4395   if (isPartialSpecialization) {
4396     if (CheckClassTemplatePartialSpecializationArgs(*this,
4397                                          ClassTemplate->getTemplateParameters(),
4398                                          Converted))
4399       return true;
4400
4401     if (!Name.isDependent() &&
4402         !TemplateSpecializationType::anyDependentTemplateArguments(
4403                                              TemplateArgs.getArgumentArray(),
4404                                                          TemplateArgs.size())) {
4405       Diag(TemplateNameLoc, diag::err_partial_spec_fully_specialized)
4406         << ClassTemplate->getDeclName();
4407       isPartialSpecialization = false;
4408     }
4409   }
4410
4411   void *InsertPos = 0;
4412   ClassTemplateSpecializationDecl *PrevDecl = 0;
4413
4414   if (isPartialSpecialization)
4415     // FIXME: Template parameter list matters, too
4416     PrevDecl
4417       = ClassTemplate->findPartialSpecialization(Converted.data(),
4418                                                  Converted.size(),
4419                                                  InsertPos);
4420   else
4421     PrevDecl
4422       = ClassTemplate->findSpecialization(Converted.data(),
4423                                           Converted.size(), InsertPos);
4424
4425   ClassTemplateSpecializationDecl *Specialization = 0;
4426
4427   // Check whether we can declare a class template specialization in
4428   // the current scope.
4429   if (TUK != TUK_Friend &&
4430       CheckTemplateSpecializationScope(*this, ClassTemplate, PrevDecl,
4431                                        TemplateNameLoc,
4432                                        isPartialSpecialization))
4433     return true;
4434
4435   // The canonical type
4436   QualType CanonType;
4437   if (PrevDecl &&
4438       (PrevDecl->getSpecializationKind() == TSK_Undeclared ||
4439                TUK == TUK_Friend)) {
4440     // Since the only prior class template specialization with these
4441     // arguments was referenced but not declared, or we're only
4442     // referencing this specialization as a friend, reuse that
4443     // declaration node as our own, updating its source location to
4444     // reflect our new declaration.
4445     Specialization = PrevDecl;
4446     Specialization->setLocation(TemplateNameLoc);
4447     PrevDecl = 0;
4448     CanonType = Context.getTypeDeclType(Specialization);
4449   } else if (isPartialSpecialization) {
4450     // Build the canonical type that describes the converted template
4451     // arguments of the class template partial specialization.
4452     TemplateName CanonTemplate = Context.getCanonicalTemplateName(Name);
4453     CanonType = Context.getTemplateSpecializationType(CanonTemplate,
4454                                                       Converted.data(),
4455                                                       Converted.size());
4456
4457     if (Context.hasSameType(CanonType,
4458                         ClassTemplate->getInjectedClassNameSpecialization())) {
4459       // C++ [temp.class.spec]p9b3:
4460       //
4461       //   -- The argument list of the specialization shall not be identical
4462       //      to the implicit argument list of the primary template.
4463       Diag(TemplateNameLoc, diag::err_partial_spec_args_match_primary_template)
4464       << (TUK == TUK_Definition)
4465       << FixItHint::CreateRemoval(SourceRange(LAngleLoc, RAngleLoc));
4466       return CheckClassTemplate(S, TagSpec, TUK, KWLoc, SS,
4467                                 ClassTemplate->getIdentifier(),
4468                                 TemplateNameLoc,
4469                                 Attr,
4470                                 TemplateParams,
4471                                 AS_none);
4472     }
4473
4474     // Create a new class template partial specialization declaration node.
4475     ClassTemplatePartialSpecializationDecl *PrevPartial
4476       = cast_or_null<ClassTemplatePartialSpecializationDecl>(PrevDecl);
4477     unsigned SequenceNumber = PrevPartial? PrevPartial->getSequenceNumber()
4478                             : ClassTemplate->getNextPartialSpecSequenceNumber();
4479     ClassTemplatePartialSpecializationDecl *Partial
4480       = ClassTemplatePartialSpecializationDecl::Create(Context, Kind,
4481                                              ClassTemplate->getDeclContext(),
4482                                                        TemplateNameLoc,
4483                                                        TemplateParams,
4484                                                        ClassTemplate,
4485                                                        Converted.data(),
4486                                                        Converted.size(),
4487                                                        TemplateArgs,
4488                                                        CanonType,
4489                                                        PrevPartial,
4490                                                        SequenceNumber);
4491     SetNestedNameSpecifier(Partial, SS);
4492     if (NumMatchedTemplateParamLists > 0 && SS.isSet()) {
4493       Partial->setTemplateParameterListsInfo(Context,
4494                                              NumMatchedTemplateParamLists,
4495                     (TemplateParameterList**) TemplateParameterLists.release());
4496     }
4497
4498     if (!PrevPartial)
4499       ClassTemplate->AddPartialSpecialization(Partial, InsertPos);
4500     Specialization = Partial;
4501
4502     // If we are providing an explicit specialization of a member class
4503     // template specialization, make a note of that.
4504     if (PrevPartial && PrevPartial->getInstantiatedFromMember())
4505       PrevPartial->setMemberSpecialization();
4506
4507     // Check that all of the template parameters of the class template
4508     // partial specialization are deducible from the template
4509     // arguments. If not, this class template partial specialization
4510     // will never be used.
4511     llvm::SmallVector<bool, 8> DeducibleParams;
4512     DeducibleParams.resize(TemplateParams->size());
4513     MarkUsedTemplateParameters(Partial->getTemplateArgs(), true,
4514                                TemplateParams->getDepth(),
4515                                DeducibleParams);
4516     unsigned NumNonDeducible = 0;
4517     for (unsigned I = 0, N = DeducibleParams.size(); I != N; ++I)
4518       if (!DeducibleParams[I])
4519         ++NumNonDeducible;
4520
4521     if (NumNonDeducible) {
4522       Diag(TemplateNameLoc, diag::warn_partial_specs_not_deducible)
4523         << (NumNonDeducible > 1)
4524         << SourceRange(TemplateNameLoc, RAngleLoc);
4525       for (unsigned I = 0, N = DeducibleParams.size(); I != N; ++I) {
4526         if (!DeducibleParams[I]) {
4527           NamedDecl *Param = cast<NamedDecl>(TemplateParams->getParam(I));
4528           if (Param->getDeclName())
4529             Diag(Param->getLocation(),
4530                  diag::note_partial_spec_unused_parameter)
4531               << Param->getDeclName();
4532           else
4533             Diag(Param->getLocation(),
4534                  diag::note_partial_spec_unused_parameter)
4535               << "<anonymous>";
4536         }
4537       }
4538     }
4539   } else {
4540     // Create a new class template specialization declaration node for
4541     // this explicit specialization or friend declaration.
4542     Specialization
4543       = ClassTemplateSpecializationDecl::Create(Context, Kind,
4544                                              ClassTemplate->getDeclContext(),
4545                                                 TemplateNameLoc,
4546                                                 ClassTemplate,
4547                                                 Converted.data(),
4548                                                 Converted.size(),
4549                                                 PrevDecl);
4550     SetNestedNameSpecifier(Specialization, SS);
4551     if (NumMatchedTemplateParamLists > 0 && SS.isSet()) {
4552       Specialization->setTemplateParameterListsInfo(Context,
4553                                                   NumMatchedTemplateParamLists,
4554                     (TemplateParameterList**) TemplateParameterLists.release());
4555     }
4556
4557     if (!PrevDecl)
4558       ClassTemplate->AddSpecialization(Specialization, InsertPos);
4559
4560     CanonType = Context.getTypeDeclType(Specialization);
4561   }
4562
4563   // C++ [temp.expl.spec]p6:
4564   //   If a template, a member template or the member of a class template is
4565   //   explicitly specialized then that specialization shall be declared
4566   //   before the first use of that specialization that would cause an implicit
4567   //   instantiation to take place, in every translation unit in which such a
4568   //   use occurs; no diagnostic is required.
4569   if (PrevDecl && PrevDecl->getPointOfInstantiation().isValid()) {
4570     bool Okay = false;
4571     for (NamedDecl *Prev = PrevDecl; Prev; Prev = getPreviousDecl(Prev)) {
4572       // Is there any previous explicit specialization declaration?
4573       if (getTemplateSpecializationKind(Prev) == TSK_ExplicitSpecialization) {
4574         Okay = true;
4575         break;
4576       }
4577     }
4578
4579     if (!Okay) {
4580       SourceRange Range(TemplateNameLoc, RAngleLoc);
4581       Diag(TemplateNameLoc, diag::err_specialization_after_instantiation)
4582         << Context.getTypeDeclType(Specialization) << Range;
4583
4584       Diag(PrevDecl->getPointOfInstantiation(),
4585            diag::note_instantiation_required_here)
4586         << (PrevDecl->getTemplateSpecializationKind()
4587                                                 != TSK_ImplicitInstantiation);
4588       return true;
4589     }
4590   }
4591
4592   // If this is not a friend, note that this is an explicit specialization.
4593   if (TUK != TUK_Friend)
4594     Specialization->setSpecializationKind(TSK_ExplicitSpecialization);
4595
4596   // Check that this isn't a redefinition of this specialization.
4597   if (TUK == TUK_Definition) {
4598     if (RecordDecl *Def = Specialization->getDefinition()) {
4599       SourceRange Range(TemplateNameLoc, RAngleLoc);
4600       Diag(TemplateNameLoc, diag::err_redefinition)
4601         << Context.getTypeDeclType(Specialization) << Range;
4602       Diag(Def->getLocation(), diag::note_previous_definition);
4603       Specialization->setInvalidDecl();
4604       return true;
4605     }
4606   }
4607
4608   if (Attr)
4609     ProcessDeclAttributeList(S, Specialization, Attr);
4610
4611   // Build the fully-sugared type for this class template
4612   // specialization as the user wrote in the specialization
4613   // itself. This means that we'll pretty-print the type retrieved
4614   // from the specialization's declaration the way that the user
4615   // actually wrote the specialization, rather than formatting the
4616   // name based on the "canonical" representation used to store the
4617   // template arguments in the specialization.
4618   TypeSourceInfo *WrittenTy
4619     = Context.getTemplateSpecializationTypeInfo(Name, TemplateNameLoc,
4620                                                 TemplateArgs, CanonType);
4621   if (TUK != TUK_Friend) {
4622     Specialization->setTypeAsWritten(WrittenTy);
4623     if (TemplateParams)
4624       Specialization->setTemplateKeywordLoc(TemplateParams->getTemplateLoc());
4625   }
4626   TemplateArgsIn.release();
4627
4628   // C++ [temp.expl.spec]p9:
4629   //   A template explicit specialization is in the scope of the
4630   //   namespace in which the template was defined.
4631   //
4632   // We actually implement this paragraph where we set the semantic
4633   // context (in the creation of the ClassTemplateSpecializationDecl),
4634   // but we also maintain the lexical context where the actual
4635   // definition occurs.
4636   Specialization->setLexicalDeclContext(CurContext);
4637
4638   // We may be starting the definition of this specialization.
4639   if (TUK == TUK_Definition)
4640     Specialization->startDefinition();
4641
4642   if (TUK == TUK_Friend) {
4643     FriendDecl *Friend = FriendDecl::Create(Context, CurContext,
4644                                             TemplateNameLoc,
4645                                             WrittenTy,
4646                                             /*FIXME:*/KWLoc);
4647     Friend->setAccess(AS_public);
4648     CurContext->addDecl(Friend);
4649   } else {
4650     // Add the specialization into its lexical context, so that it can
4651     // be seen when iterating through the list of declarations in that
4652     // context. However, specializations are not found by name lookup.
4653     CurContext->addDecl(Specialization);
4654   }
4655   return Specialization;
4656 }
4657
4658 Decl *Sema::ActOnTemplateDeclarator(Scope *S,
4659                               MultiTemplateParamsArg TemplateParameterLists,
4660                                     Declarator &D) {
4661   return HandleDeclarator(S, D, move(TemplateParameterLists), false);
4662 }
4663
4664 Decl *Sema::ActOnStartOfFunctionTemplateDef(Scope *FnBodyScope,
4665                                MultiTemplateParamsArg TemplateParameterLists,
4666                                             Declarator &D) {
4667   assert(getCurFunctionDecl() == 0 && "Function parsing confused");
4668   DeclaratorChunk::FunctionTypeInfo &FTI = D.getFunctionTypeInfo();
4669
4670   if (FTI.hasPrototype) {
4671     // FIXME: Diagnose arguments without names in C.
4672   }
4673
4674   Scope *ParentScope = FnBodyScope->getParent();
4675
4676   Decl *DP = HandleDeclarator(ParentScope, D,
4677                               move(TemplateParameterLists),
4678                               /*IsFunctionDefinition=*/true);
4679   if (FunctionTemplateDecl *FunctionTemplate
4680         = dyn_cast_or_null<FunctionTemplateDecl>(DP))
4681     return ActOnStartOfFunctionDef(FnBodyScope,
4682                                    FunctionTemplate->getTemplatedDecl());
4683   if (FunctionDecl *Function = dyn_cast_or_null<FunctionDecl>(DP))
4684     return ActOnStartOfFunctionDef(FnBodyScope, Function);
4685   return 0;
4686 }
4687
4688 /// \brief Strips various properties off an implicit instantiation
4689 /// that has just been explicitly specialized.
4690 static void StripImplicitInstantiation(NamedDecl *D) {
4691   D->dropAttrs();
4692
4693   if (FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) {
4694     FD->setInlineSpecified(false);
4695   }
4696 }
4697
4698 /// \brief Diagnose cases where we have an explicit template specialization
4699 /// before/after an explicit template instantiation, producing diagnostics
4700 /// for those cases where they are required and determining whether the
4701 /// new specialization/instantiation will have any effect.
4702 ///
4703 /// \param NewLoc the location of the new explicit specialization or
4704 /// instantiation.
4705 ///
4706 /// \param NewTSK the kind of the new explicit specialization or instantiation.
4707 ///
4708 /// \param PrevDecl the previous declaration of the entity.
4709 ///
4710 /// \param PrevTSK the kind of the old explicit specialization or instantiatin.
4711 ///
4712 /// \param PrevPointOfInstantiation if valid, indicates where the previus
4713 /// declaration was instantiated (either implicitly or explicitly).
4714 ///
4715 /// \param HasNoEffect will be set to true to indicate that the new
4716 /// specialization or instantiation has no effect and should be ignored.
4717 ///
4718 /// \returns true if there was an error that should prevent the introduction of
4719 /// the new declaration into the AST, false otherwise.
4720 bool
4721 Sema::CheckSpecializationInstantiationRedecl(SourceLocation NewLoc,
4722                                              TemplateSpecializationKind NewTSK,
4723                                              NamedDecl *PrevDecl,
4724                                              TemplateSpecializationKind PrevTSK,
4725                                         SourceLocation PrevPointOfInstantiation,
4726                                              bool &HasNoEffect) {
4727   HasNoEffect = false;
4728
4729   switch (NewTSK) {
4730   case TSK_Undeclared:
4731   case TSK_ImplicitInstantiation:
4732     assert(false && "Don't check implicit instantiations here");
4733     return false;
4734
4735   case TSK_ExplicitSpecialization:
4736     switch (PrevTSK) {
4737     case TSK_Undeclared:
4738     case TSK_ExplicitSpecialization:
4739       // Okay, we're just specializing something that is either already
4740       // explicitly specialized or has merely been mentioned without any
4741       // instantiation.
4742       return false;
4743
4744     case TSK_ImplicitInstantiation:
4745       if (PrevPointOfInstantiation.isInvalid()) {
4746         // The declaration itself has not actually been instantiated, so it is
4747         // still okay to specialize it.
4748         StripImplicitInstantiation(PrevDecl);
4749         return false;
4750       }
4751       // Fall through
4752
4753     case TSK_ExplicitInstantiationDeclaration:
4754     case TSK_ExplicitInstantiationDefinition:
4755       assert((PrevTSK == TSK_ImplicitInstantiation ||
4756               PrevPointOfInstantiation.isValid()) &&
4757              "Explicit instantiation without point of instantiation?");
4758
4759       // C++ [temp.expl.spec]p6:
4760       //   If a template, a member template or the member of a class template
4761       //   is explicitly specialized then that specialization shall be declared
4762       //   before the first use of that specialization that would cause an
4763       //   implicit instantiation to take place, in every translation unit in
4764       //   which such a use occurs; no diagnostic is required.
4765       for (NamedDecl *Prev = PrevDecl; Prev; Prev = getPreviousDecl(Prev)) {
4766         // Is there any previous explicit specialization declaration?
4767         if (getTemplateSpecializationKind(Prev) == TSK_ExplicitSpecialization)
4768           return false;
4769       }
4770
4771       Diag(NewLoc, diag::err_specialization_after_instantiation)
4772         << PrevDecl;
4773       Diag(PrevPointOfInstantiation, diag::note_instantiation_required_here)
4774         << (PrevTSK != TSK_ImplicitInstantiation);
4775
4776       return true;
4777     }
4778     break;
4779
4780   case TSK_ExplicitInstantiationDeclaration:
4781     switch (PrevTSK) {
4782     case TSK_ExplicitInstantiationDeclaration:
4783       // This explicit instantiation declaration is redundant (that's okay).
4784       HasNoEffect = true;
4785       return false;
4786
4787     case TSK_Undeclared:
4788     case TSK_ImplicitInstantiation:
4789       // We're explicitly instantiating something that may have already been
4790       // implicitly instantiated; that's fine.
4791       return false;
4792
4793     case TSK_ExplicitSpecialization:
4794       // C++0x [temp.explicit]p4:
4795       //   For a given set of template parameters, if an explicit instantiation
4796       //   of a template appears after a declaration of an explicit
4797       //   specialization for that template, the explicit instantiation has no
4798       //   effect.
4799       HasNoEffect = true;
4800       return false;
4801
4802     case TSK_ExplicitInstantiationDefinition:
4803       // C++0x [temp.explicit]p10:
4804       //   If an entity is the subject of both an explicit instantiation
4805       //   declaration and an explicit instantiation definition in the same
4806       //   translation unit, the definition shall follow the declaration.
4807       Diag(NewLoc,
4808            diag::err_explicit_instantiation_declaration_after_definition);
4809       Diag(PrevPointOfInstantiation,
4810            diag::note_explicit_instantiation_definition_here);
4811       assert(PrevPointOfInstantiation.isValid() &&
4812              "Explicit instantiation without point of instantiation?");
4813       HasNoEffect = true;
4814       return false;
4815     }
4816     break;
4817
4818   case TSK_ExplicitInstantiationDefinition:
4819     switch (PrevTSK) {
4820     case TSK_Undeclared:
4821     case TSK_ImplicitInstantiation:
4822       // We're explicitly instantiating something that may have already been
4823       // implicitly instantiated; that's fine.
4824       return false;
4825
4826     case TSK_ExplicitSpecialization:
4827       // C++ DR 259, C++0x [temp.explicit]p4:
4828       //   For a given set of template parameters, if an explicit
4829       //   instantiation of a template appears after a declaration of
4830       //   an explicit specialization for that template, the explicit
4831       //   instantiation has no effect.
4832       //
4833       // In C++98/03 mode, we only give an extension warning here, because it
4834       // is not harmful to try to explicitly instantiate something that
4835       // has been explicitly specialized.
4836       if (!getLangOptions().CPlusPlus0x) {
4837         Diag(NewLoc, diag::ext_explicit_instantiation_after_specialization)
4838           << PrevDecl;
4839         Diag(PrevDecl->getLocation(),
4840              diag::note_previous_template_specialization);
4841       }
4842       HasNoEffect = true;
4843       return false;
4844
4845     case TSK_ExplicitInstantiationDeclaration:
4846       // We're explicity instantiating a definition for something for which we
4847       // were previously asked to suppress instantiations. That's fine.
4848       return false;
4849
4850     case TSK_ExplicitInstantiationDefinition:
4851       // C++0x [temp.spec]p5:
4852       //   For a given template and a given set of template-arguments,
4853       //     - an explicit instantiation definition shall appear at most once
4854       //       in a program,
4855       Diag(NewLoc, diag::err_explicit_instantiation_duplicate)
4856         << PrevDecl;
4857       Diag(PrevPointOfInstantiation,
4858            diag::note_previous_explicit_instantiation);
4859       HasNoEffect = true;
4860       return false;
4861     }
4862     break;
4863   }
4864
4865   assert(false && "Missing specialization/instantiation case?");
4866
4867   return false;
4868 }
4869
4870 /// \brief Perform semantic analysis for the given dependent function
4871 /// template specialization.  The only possible way to get a dependent
4872 /// function template specialization is with a friend declaration,
4873 /// like so:
4874 ///
4875 ///   template <class T> void foo(T);
4876 ///   template <class T> class A {
4877 ///     friend void foo<>(T);
4878 ///   };
4879 ///
4880 /// There really isn't any useful analysis we can do here, so we
4881 /// just store the information.
4882 bool
4883 Sema::CheckDependentFunctionTemplateSpecialization(FunctionDecl *FD,
4884                    const TemplateArgumentListInfo &ExplicitTemplateArgs,
4885                                                    LookupResult &Previous) {
4886   // Remove anything from Previous that isn't a function template in
4887   // the correct context.
4888   DeclContext *FDLookupContext = FD->getDeclContext()->getRedeclContext();
4889   LookupResult::Filter F = Previous.makeFilter();
4890   while (F.hasNext()) {
4891     NamedDecl *D = F.next()->getUnderlyingDecl();
4892     if (!isa<FunctionTemplateDecl>(D) ||
4893         !FDLookupContext->InEnclosingNamespaceSetOf(
4894                               D->getDeclContext()->getRedeclContext()))
4895       F.erase();
4896   }
4897   F.done();
4898
4899   // Should this be diagnosed here?
4900   if (Previous.empty()) return true;
4901
4902   FD->setDependentTemplateSpecialization(Context, Previous.asUnresolvedSet(),
4903                                          ExplicitTemplateArgs);
4904   return false;
4905 }
4906
4907 /// \brief Perform semantic analysis for the given function template
4908 /// specialization.
4909 ///
4910 /// This routine performs all of the semantic analysis required for an
4911 /// explicit function template specialization. On successful completion,
4912 /// the function declaration \p FD will become a function template
4913 /// specialization.
4914 ///
4915 /// \param FD the function declaration, which will be updated to become a
4916 /// function template specialization.
4917 ///
4918 /// \param ExplicitTemplateArgs the explicitly-provided template arguments,
4919 /// if any. Note that this may be valid info even when 0 arguments are
4920 /// explicitly provided as in, e.g., \c void sort<>(char*, char*);
4921 /// as it anyway contains info on the angle brackets locations.
4922 ///
4923 /// \param PrevDecl the set of declarations that may be specialized by
4924 /// this function specialization.
4925 bool
4926 Sema::CheckFunctionTemplateSpecialization(FunctionDecl *FD,
4927                         const TemplateArgumentListInfo *ExplicitTemplateArgs,
4928                                           LookupResult &Previous) {
4929   // The set of function template specializations that could match this
4930   // explicit function template specialization.
4931   UnresolvedSet<8> Candidates;
4932
4933   DeclContext *FDLookupContext = FD->getDeclContext()->getRedeclContext();
4934   for (LookupResult::iterator I = Previous.begin(), E = Previous.end();
4935          I != E; ++I) {
4936     NamedDecl *Ovl = (*I)->getUnderlyingDecl();
4937     if (FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(Ovl)) {
4938       // Only consider templates found within the same semantic lookup scope as
4939       // FD.
4940       if (!FDLookupContext->InEnclosingNamespaceSetOf(
4941                                 Ovl->getDeclContext()->getRedeclContext()))
4942         continue;
4943
4944       // C++ [temp.expl.spec]p11:
4945       //   A trailing template-argument can be left unspecified in the
4946       //   template-id naming an explicit function template specialization
4947       //   provided it can be deduced from the function argument type.
4948       // Perform template argument deduction to determine whether we may be
4949       // specializing this template.
4950       // FIXME: It is somewhat wasteful to build
4951       TemplateDeductionInfo Info(Context, FD->getLocation());
4952       FunctionDecl *Specialization = 0;
4953       if (TemplateDeductionResult TDK
4954             = DeduceTemplateArguments(FunTmpl, ExplicitTemplateArgs,
4955                                       FD->getType(),
4956                                       Specialization,
4957                                       Info)) {
4958         // FIXME: Template argument deduction failed; record why it failed, so
4959         // that we can provide nifty diagnostics.
4960         (void)TDK;
4961         continue;
4962       }
4963
4964       // Record this candidate.
4965       Candidates.addDecl(Specialization, I.getAccess());
4966     }
4967   }
4968
4969   // Find the most specialized function template.
4970   UnresolvedSetIterator Result
4971     = getMostSpecialized(Candidates.begin(), Candidates.end(),
4972                          TPOC_Other, 0, FD->getLocation(),
4973                   PDiag(diag::err_function_template_spec_no_match)
4974                     << FD->getDeclName(),
4975                   PDiag(diag::err_function_template_spec_ambiguous)
4976                     << FD->getDeclName() << (ExplicitTemplateArgs != 0),
4977                   PDiag(diag::note_function_template_spec_matched));
4978   if (Result == Candidates.end())
4979     return true;
4980
4981   // Ignore access information;  it doesn't figure into redeclaration checking.
4982   FunctionDecl *Specialization = cast<FunctionDecl>(*Result);
4983   Specialization->setLocation(FD->getLocation());
4984
4985   // FIXME: Check if the prior specialization has a point of instantiation.
4986   // If so, we have run afoul of .
4987
4988   // If this is a friend declaration, then we're not really declaring
4989   // an explicit specialization.
4990   bool isFriend = (FD->getFriendObjectKind() != Decl::FOK_None);
4991
4992   // Check the scope of this explicit specialization.
4993   if (!isFriend &&
4994       CheckTemplateSpecializationScope(*this,
4995                                        Specialization->getPrimaryTemplate(),
4996                                        Specialization, FD->getLocation(),
4997                                        false))
4998     return true;
4999
5000   // C++ [temp.expl.spec]p6:
5001   //   If a template, a member template or the member of a class template is
5002   //   explicitly specialized then that specialization shall be declared
5003   //   before the first use of that specialization that would cause an implicit
5004   //   instantiation to take place, in every translation unit in which such a
5005   //   use occurs; no diagnostic is required.
5006   FunctionTemplateSpecializationInfo *SpecInfo
5007     = Specialization->getTemplateSpecializationInfo();
5008   assert(SpecInfo && "Function template specialization info missing?");
5009
5010   bool HasNoEffect = false;
5011   if (!isFriend &&
5012       CheckSpecializationInstantiationRedecl(FD->getLocation(),
5013                                              TSK_ExplicitSpecialization,
5014                                              Specialization,
5015                                    SpecInfo->getTemplateSpecializationKind(),
5016                                          SpecInfo->getPointOfInstantiation(),
5017                                              HasNoEffect))
5018     return true;
5019
5020   // Mark the prior declaration as an explicit specialization, so that later
5021   // clients know that this is an explicit specialization.
5022   if (!isFriend) {
5023     SpecInfo->setTemplateSpecializationKind(TSK_ExplicitSpecialization);
5024     MarkUnusedFileScopedDecl(Specialization);
5025   }
5026
5027   // Turn the given function declaration into a function template
5028   // specialization, with the template arguments from the previous
5029   // specialization.
5030   // Take copies of (semantic and syntactic) template argument lists.
5031   const TemplateArgumentList* TemplArgs = new (Context)
5032     TemplateArgumentList(Specialization->getTemplateSpecializationArgs());
5033   const TemplateArgumentListInfo* TemplArgsAsWritten = ExplicitTemplateArgs
5034     ? new (Context) TemplateArgumentListInfo(*ExplicitTemplateArgs) : 0;
5035   FD->setFunctionTemplateSpecialization(Specialization->getPrimaryTemplate(),
5036                                         TemplArgs, /*InsertPos=*/0,
5037                                     SpecInfo->getTemplateSpecializationKind(),
5038                                         TemplArgsAsWritten);
5039
5040   // The "previous declaration" for this function template specialization is
5041   // the prior function template specialization.
5042   Previous.clear();
5043   Previous.addDecl(Specialization);
5044   return false;
5045 }
5046
5047 /// \brief Perform semantic analysis for the given non-template member
5048 /// specialization.
5049 ///
5050 /// This routine performs all of the semantic analysis required for an
5051 /// explicit member function specialization. On successful completion,
5052 /// the function declaration \p FD will become a member function
5053 /// specialization.
5054 ///
5055 /// \param Member the member declaration, which will be updated to become a
5056 /// specialization.
5057 ///
5058 /// \param Previous the set of declarations, one of which may be specialized
5059 /// by this function specialization;  the set will be modified to contain the
5060 /// redeclared member.
5061 bool
5062 Sema::CheckMemberSpecialization(NamedDecl *Member, LookupResult &Previous) {
5063   assert(!isa<TemplateDecl>(Member) && "Only for non-template members");
5064
5065   // Try to find the member we are instantiating.
5066   NamedDecl *Instantiation = 0;
5067   NamedDecl *InstantiatedFrom = 0;
5068   MemberSpecializationInfo *MSInfo = 0;
5069
5070   if (Previous.empty()) {
5071     // Nowhere to look anyway.
5072   } else if (FunctionDecl *Function = dyn_cast<FunctionDecl>(Member)) {
5073     for (LookupResult::iterator I = Previous.begin(), E = Previous.end();
5074            I != E; ++I) {
5075       NamedDecl *D = (*I)->getUnderlyingDecl();
5076       if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(D)) {
5077         if (Context.hasSameType(Function->getType(), Method->getType())) {
5078           Instantiation = Method;
5079           InstantiatedFrom = Method->getInstantiatedFromMemberFunction();
5080           MSInfo = Method->getMemberSpecializationInfo();
5081           break;
5082         }
5083       }
5084     }
5085   } else if (isa<VarDecl>(Member)) {
5086     VarDecl *PrevVar;
5087     if (Previous.isSingleResult() &&
5088         (PrevVar = dyn_cast<VarDecl>(Previous.getFoundDecl())))
5089       if (PrevVar->isStaticDataMember()) {
5090         Instantiation = PrevVar;
5091         InstantiatedFrom = PrevVar->getInstantiatedFromStaticDataMember();
5092         MSInfo = PrevVar->getMemberSpecializationInfo();
5093       }
5094   } else if (isa<RecordDecl>(Member)) {
5095     CXXRecordDecl *PrevRecord;
5096     if (Previous.isSingleResult() &&
5097         (PrevRecord = dyn_cast<CXXRecordDecl>(Previous.getFoundDecl()))) {
5098       Instantiation = PrevRecord;
5099       InstantiatedFrom = PrevRecord->getInstantiatedFromMemberClass();
5100       MSInfo = PrevRecord->getMemberSpecializationInfo();
5101     }
5102   }
5103
5104   if (!Instantiation) {
5105     // There is no previous declaration that matches. Since member
5106     // specializations are always out-of-line, the caller will complain about
5107     // this mismatch later.
5108     return false;
5109   }
5110
5111   // If this is a friend, just bail out here before we start turning
5112   // things into explicit specializations.
5113   if (Member->getFriendObjectKind() != Decl::FOK_None) {
5114     // Preserve instantiation information.
5115     if (InstantiatedFrom && isa<CXXMethodDecl>(Member)) {
5116       cast<CXXMethodDecl>(Member)->setInstantiationOfMemberFunction(
5117                                       cast<CXXMethodDecl>(InstantiatedFrom),
5118         cast<CXXMethodDecl>(Instantiation)->getTemplateSpecializationKind());
5119     } else if (InstantiatedFrom && isa<CXXRecordDecl>(Member)) {
5120       cast<CXXRecordDecl>(Member)->setInstantiationOfMemberClass(
5121                                       cast<CXXRecordDecl>(InstantiatedFrom),
5122         cast<CXXRecordDecl>(Instantiation)->getTemplateSpecializationKind());
5123     }
5124
5125     Previous.clear();
5126     Previous.addDecl(Instantiation);
5127     return false;
5128   }
5129
5130   // Make sure that this is a specialization of a member.
5131   if (!InstantiatedFrom) {
5132     Diag(Member->getLocation(), diag::err_spec_member_not_instantiated)
5133       << Member;
5134     Diag(Instantiation->getLocation(), diag::note_specialized_decl);
5135     return true;
5136   }
5137
5138   // C++ [temp.expl.spec]p6:
5139   //   If a template, a member template or the member of a class template is
5140   //   explicitly specialized then that spe- cialization shall be declared
5141   //   before the first use of that specialization that would cause an implicit
5142   //   instantiation to take place, in every translation unit in which such a
5143   //   use occurs; no diagnostic is required.
5144   assert(MSInfo && "Member specialization info missing?");
5145
5146   bool HasNoEffect = false;
5147   if (CheckSpecializationInstantiationRedecl(Member->getLocation(),
5148                                              TSK_ExplicitSpecialization,
5149                                              Instantiation,
5150                                      MSInfo->getTemplateSpecializationKind(),
5151                                            MSInfo->getPointOfInstantiation(),
5152                                              HasNoEffect))
5153     return true;
5154
5155   // Check the scope of this explicit specialization.
5156   if (CheckTemplateSpecializationScope(*this,
5157                                        InstantiatedFrom,
5158                                        Instantiation, Member->getLocation(),
5159                                        false))
5160     return true;
5161
5162   // Note that this is an explicit instantiation of a member.
5163   // the original declaration to note that it is an explicit specialization
5164   // (if it was previously an implicit instantiation). This latter step
5165   // makes bookkeeping easier.
5166   if (isa<FunctionDecl>(Member)) {
5167     FunctionDecl *InstantiationFunction = cast<FunctionDecl>(Instantiation);
5168     if (InstantiationFunction->getTemplateSpecializationKind() ==
5169           TSK_ImplicitInstantiation) {
5170       InstantiationFunction->setTemplateSpecializationKind(
5171                                                   TSK_ExplicitSpecialization);
5172       InstantiationFunction->setLocation(Member->getLocation());
5173     }
5174
5175     cast<FunctionDecl>(Member)->setInstantiationOfMemberFunction(
5176                                         cast<CXXMethodDecl>(InstantiatedFrom),
5177                                                   TSK_ExplicitSpecialization);
5178     MarkUnusedFileScopedDecl(InstantiationFunction);
5179   } else if (isa<VarDecl>(Member)) {
5180     VarDecl *InstantiationVar = cast<VarDecl>(Instantiation);
5181     if (InstantiationVar->getTemplateSpecializationKind() ==
5182           TSK_ImplicitInstantiation) {
5183       InstantiationVar->setTemplateSpecializationKind(
5184                                                   TSK_ExplicitSpecialization);
5185       InstantiationVar->setLocation(Member->getLocation());
5186     }
5187
5188     Context.setInstantiatedFromStaticDataMember(cast<VarDecl>(Member),
5189                                                 cast<VarDecl>(InstantiatedFrom),
5190                                                 TSK_ExplicitSpecialization);
5191     MarkUnusedFileScopedDecl(InstantiationVar);
5192   } else {
5193     assert(isa<CXXRecordDecl>(Member) && "Only member classes remain");
5194     CXXRecordDecl *InstantiationClass = cast<CXXRecordDecl>(Instantiation);
5195     if (InstantiationClass->getTemplateSpecializationKind() ==
5196           TSK_ImplicitInstantiation) {
5197       InstantiationClass->setTemplateSpecializationKind(
5198                                                    TSK_ExplicitSpecialization);
5199       InstantiationClass->setLocation(Member->getLocation());
5200     }
5201
5202     cast<CXXRecordDecl>(Member)->setInstantiationOfMemberClass(
5203                                         cast<CXXRecordDecl>(InstantiatedFrom),
5204                                                    TSK_ExplicitSpecialization);
5205   }
5206
5207   // Save the caller the trouble of having to figure out which declaration
5208   // this specialization matches.
5209   Previous.clear();
5210   Previous.addDecl(Instantiation);
5211   return false;
5212 }
5213
5214 /// \brief Check the scope of an explicit instantiation.
5215 ///
5216 /// \returns true if a serious error occurs, false otherwise.
5217 static bool CheckExplicitInstantiationScope(Sema &S, NamedDecl *D,
5218                                             SourceLocation InstLoc,
5219                                             bool WasQualifiedName) {
5220   DeclContext *OrigContext= D->getDeclContext()->getEnclosingNamespaceContext();
5221   DeclContext *CurContext = S.CurContext->getRedeclContext();
5222
5223   if (CurContext->isRecord()) {
5224     S.Diag(InstLoc, diag::err_explicit_instantiation_in_class)
5225       << D;
5226     return true;
5227   }
5228
5229   // C++0x [temp.explicit]p2:
5230   //   An explicit instantiation shall appear in an enclosing namespace of its
5231   //   template.
5232   //
5233   // This is DR275, which we do not retroactively apply to C++98/03.
5234   if (S.getLangOptions().CPlusPlus0x &&
5235       !CurContext->Encloses(OrigContext)) {
5236     if (NamespaceDecl *NS = dyn_cast<NamespaceDecl>(OrigContext))
5237       S.Diag(InstLoc,
5238              S.getLangOptions().CPlusPlus0x?
5239                  diag::err_explicit_instantiation_out_of_scope
5240                : diag::warn_explicit_instantiation_out_of_scope_0x)
5241         << D << NS;
5242     else
5243       S.Diag(InstLoc,
5244              S.getLangOptions().CPlusPlus0x?
5245                  diag::err_explicit_instantiation_must_be_global
5246                : diag::warn_explicit_instantiation_out_of_scope_0x)
5247         << D;
5248     S.Diag(D->getLocation(), diag::note_explicit_instantiation_here);
5249     return false;
5250   }
5251
5252   // C++0x [temp.explicit]p2:
5253   //   If the name declared in the explicit instantiation is an unqualified
5254   //   name, the explicit instantiation shall appear in the namespace where
5255   //   its template is declared or, if that namespace is inline (7.3.1), any
5256   //   namespace from its enclosing namespace set.
5257   if (WasQualifiedName)
5258     return false;
5259
5260   if (CurContext->InEnclosingNamespaceSetOf(OrigContext))
5261     return false;
5262
5263   S.Diag(InstLoc,
5264          S.getLangOptions().CPlusPlus0x?
5265              diag::err_explicit_instantiation_unqualified_wrong_namespace
5266            : diag::warn_explicit_instantiation_unqualified_wrong_namespace_0x)
5267     << D << OrigContext;
5268   S.Diag(D->getLocation(), diag::note_explicit_instantiation_here);
5269   return false;
5270 }
5271
5272 /// \brief Determine whether the given scope specifier has a template-id in it.
5273 static bool ScopeSpecifierHasTemplateId(const CXXScopeSpec &SS) {
5274   if (!SS.isSet())
5275     return false;
5276
5277   // C++0x [temp.explicit]p2:
5278   //   If the explicit instantiation is for a member function, a member class
5279   //   or a static data member of a class template specialization, the name of
5280   //   the class template specialization in the qualified-id for the member
5281   //   name shall be a simple-template-id.
5282   //
5283   // C++98 has the same restriction, just worded differently.
5284   for (NestedNameSpecifier *NNS = (NestedNameSpecifier *)SS.getScopeRep();
5285        NNS; NNS = NNS->getPrefix())
5286     if (const Type *T = NNS->getAsType())
5287       if (isa<TemplateSpecializationType>(T))
5288         return true;
5289
5290   return false;
5291 }
5292
5293 // Explicit instantiation of a class template specialization
5294 DeclResult
5295 Sema::ActOnExplicitInstantiation(Scope *S,
5296                                  SourceLocation ExternLoc,
5297                                  SourceLocation TemplateLoc,
5298                                  unsigned TagSpec,
5299                                  SourceLocation KWLoc,
5300                                  const CXXScopeSpec &SS,
5301                                  TemplateTy TemplateD,
5302                                  SourceLocation TemplateNameLoc,
5303                                  SourceLocation LAngleLoc,
5304                                  ASTTemplateArgsPtr TemplateArgsIn,
5305                                  SourceLocation RAngleLoc,
5306                                  AttributeList *Attr) {
5307   // Find the class template we're specializing
5308   TemplateName Name = TemplateD.getAsVal<TemplateName>();
5309   ClassTemplateDecl *ClassTemplate
5310     = cast<ClassTemplateDecl>(Name.getAsTemplateDecl());
5311
5312   // Check that the specialization uses the same tag kind as the
5313   // original template.
5314   TagTypeKind Kind = TypeWithKeyword::getTagTypeKindForTypeSpec(TagSpec);
5315   assert(Kind != TTK_Enum &&
5316          "Invalid enum tag in class template explicit instantiation!");
5317   if (!isAcceptableTagRedeclaration(ClassTemplate->getTemplatedDecl(),
5318                                     Kind, KWLoc,
5319                                     *ClassTemplate->getIdentifier())) {
5320     Diag(KWLoc, diag::err_use_with_wrong_tag)
5321       << ClassTemplate
5322       << FixItHint::CreateReplacement(KWLoc,
5323                             ClassTemplate->getTemplatedDecl()->getKindName());
5324     Diag(ClassTemplate->getTemplatedDecl()->getLocation(),
5325          diag::note_previous_use);
5326     Kind = ClassTemplate->getTemplatedDecl()->getTagKind();
5327   }
5328
5329   // C++0x [temp.explicit]p2:
5330   //   There are two forms of explicit instantiation: an explicit instantiation
5331   //   definition and an explicit instantiation declaration. An explicit
5332   //   instantiation declaration begins with the extern keyword. [...]
5333   TemplateSpecializationKind TSK
5334     = ExternLoc.isInvalid()? TSK_ExplicitInstantiationDefinition
5335                            : TSK_ExplicitInstantiationDeclaration;
5336
5337   // Translate the parser's template argument list in our AST format.
5338   TemplateArgumentListInfo TemplateArgs(LAngleLoc, RAngleLoc);
5339   translateTemplateArguments(TemplateArgsIn, TemplateArgs);
5340
5341   // Check that the template argument list is well-formed for this
5342   // template.
5343   llvm::SmallVector<TemplateArgument, 4> Converted;
5344   if (CheckTemplateArgumentList(ClassTemplate, TemplateNameLoc,
5345                                 TemplateArgs, false, Converted))
5346     return true;
5347
5348   assert((Converted.size() == ClassTemplate->getTemplateParameters()->size()) &&
5349          "Converted template argument list is too short!");
5350
5351   // Find the class template specialization declaration that
5352   // corresponds to these arguments.
5353   void *InsertPos = 0;
5354   ClassTemplateSpecializationDecl *PrevDecl
5355     = ClassTemplate->findSpecialization(Converted.data(),
5356                                         Converted.size(), InsertPos);
5357
5358   TemplateSpecializationKind PrevDecl_TSK
5359     = PrevDecl ? PrevDecl->getTemplateSpecializationKind() : TSK_Undeclared;
5360
5361   // C++0x [temp.explicit]p2:
5362   //   [...] An explicit instantiation shall appear in an enclosing
5363   //   namespace of its template. [...]
5364   //
5365   // This is C++ DR 275.
5366   if (CheckExplicitInstantiationScope(*this, ClassTemplate, TemplateNameLoc,
5367                                       SS.isSet()))
5368     return true;
5369
5370   ClassTemplateSpecializationDecl *Specialization = 0;
5371
5372   bool HasNoEffect = false;
5373   if (PrevDecl) {
5374     if (CheckSpecializationInstantiationRedecl(TemplateNameLoc, TSK,
5375                                                PrevDecl, PrevDecl_TSK,
5376                                             PrevDecl->getPointOfInstantiation(),
5377                                                HasNoEffect))
5378       return PrevDecl;
5379
5380     // Even though HasNoEffect == true means that this explicit instantiation
5381     // has no effect on semantics, we go on to put its syntax in the AST.
5382
5383     if (PrevDecl_TSK == TSK_ImplicitInstantiation ||
5384         PrevDecl_TSK == TSK_Undeclared) {
5385       // Since the only prior class template specialization with these
5386       // arguments was referenced but not declared, reuse that
5387       // declaration node as our own, updating the source location
5388       // for the template name to reflect our new declaration.
5389       // (Other source locations will be updated later.)
5390       Specialization = PrevDecl;
5391       Specialization->setLocation(TemplateNameLoc);
5392       PrevDecl = 0;
5393     }
5394   }
5395
5396   if (!Specialization) {
5397     // Create a new class template specialization declaration node for
5398     // this explicit specialization.
5399     Specialization
5400       = ClassTemplateSpecializationDecl::Create(Context, Kind,
5401                                              ClassTemplate->getDeclContext(),
5402                                                 TemplateNameLoc,
5403                                                 ClassTemplate,
5404                                                 Converted.data(),
5405                                                 Converted.size(),
5406                                                 PrevDecl);
5407     SetNestedNameSpecifier(Specialization, SS);
5408
5409     if (!HasNoEffect && !PrevDecl) {
5410       // Insert the new specialization.
5411       ClassTemplate->AddSpecialization(Specialization, InsertPos);
5412     }
5413   }
5414
5415   // Build the fully-sugared type for this explicit instantiation as
5416   // the user wrote in the explicit instantiation itself. This means
5417   // that we'll pretty-print the type retrieved from the
5418   // specialization's declaration the way that the user actually wrote
5419   // the explicit instantiation, rather than formatting the name based
5420   // on the "canonical" representation used to store the template
5421   // arguments in the specialization.
5422   TypeSourceInfo *WrittenTy
5423     = Context.getTemplateSpecializationTypeInfo(Name, TemplateNameLoc,
5424                                                 TemplateArgs,
5425                                   Context.getTypeDeclType(Specialization));
5426   Specialization->setTypeAsWritten(WrittenTy);
5427   TemplateArgsIn.release();
5428
5429   // Set source locations for keywords.
5430   Specialization->setExternLoc(ExternLoc);
5431   Specialization->setTemplateKeywordLoc(TemplateLoc);
5432
5433   // Add the explicit instantiation into its lexical context. However,
5434   // since explicit instantiations are never found by name lookup, we
5435   // just put it into the declaration context directly.
5436   Specialization->setLexicalDeclContext(CurContext);
5437   CurContext->addDecl(Specialization);
5438
5439   // Syntax is now OK, so return if it has no other effect on semantics.
5440   if (HasNoEffect) {
5441     // Set the template specialization kind.
5442     Specialization->setTemplateSpecializationKind(TSK);
5443     return Specialization;
5444   }
5445
5446   // C++ [temp.explicit]p3:
5447   //   A definition of a class template or class member template
5448   //   shall be in scope at the point of the explicit instantiation of
5449   //   the class template or class member template.
5450   //
5451   // This check comes when we actually try to perform the
5452   // instantiation.
5453   ClassTemplateSpecializationDecl *Def
5454     = cast_or_null<ClassTemplateSpecializationDecl>(
5455                                               Specialization->getDefinition());
5456   if (!Def)
5457     InstantiateClassTemplateSpecialization(TemplateNameLoc, Specialization, TSK);
5458   else if (TSK == TSK_ExplicitInstantiationDefinition) {
5459     MarkVTableUsed(TemplateNameLoc, Specialization, true);
5460     Specialization->setPointOfInstantiation(Def->getPointOfInstantiation());
5461   }
5462
5463   // Instantiate the members of this class template specialization.
5464   Def = cast_or_null<ClassTemplateSpecializationDecl>(
5465                                        Specialization->getDefinition());
5466   if (Def) {
5467     TemplateSpecializationKind Old_TSK = Def->getTemplateSpecializationKind();
5468
5469     // Fix a TSK_ExplicitInstantiationDeclaration followed by a
5470     // TSK_ExplicitInstantiationDefinition
5471     if (Old_TSK == TSK_ExplicitInstantiationDeclaration &&
5472         TSK == TSK_ExplicitInstantiationDefinition)
5473       Def->setTemplateSpecializationKind(TSK);
5474
5475     InstantiateClassTemplateSpecializationMembers(TemplateNameLoc, Def, TSK);
5476   }
5477
5478   // Set the template specialization kind.
5479   Specialization->setTemplateSpecializationKind(TSK);
5480   return Specialization;
5481 }
5482
5483 // Explicit instantiation of a member class of a class template.
5484 DeclResult
5485 Sema::ActOnExplicitInstantiation(Scope *S,
5486                                  SourceLocation ExternLoc,
5487                                  SourceLocation TemplateLoc,
5488                                  unsigned TagSpec,
5489                                  SourceLocation KWLoc,
5490                                  CXXScopeSpec &SS,
5491                                  IdentifierInfo *Name,
5492                                  SourceLocation NameLoc,
5493                                  AttributeList *Attr) {
5494
5495   bool Owned = false;
5496   bool IsDependent = false;
5497   Decl *TagD = ActOnTag(S, TagSpec, Sema::TUK_Reference,
5498                         KWLoc, SS, Name, NameLoc, Attr, AS_none,
5499                         MultiTemplateParamsArg(*this, 0, 0),
5500                         Owned, IsDependent, false, false,
5501                         TypeResult());
5502   assert(!IsDependent && "explicit instantiation of dependent name not yet handled");
5503
5504   if (!TagD)
5505     return true;
5506
5507   TagDecl *Tag = cast<TagDecl>(TagD);
5508   if (Tag->isEnum()) {
5509     Diag(TemplateLoc, diag::err_explicit_instantiation_enum)
5510       << Context.getTypeDeclType(Tag);
5511     return true;
5512   }
5513
5514   if (Tag->isInvalidDecl())
5515     return true;
5516
5517   CXXRecordDecl *Record = cast<CXXRecordDecl>(Tag);
5518   CXXRecordDecl *Pattern = Record->getInstantiatedFromMemberClass();
5519   if (!Pattern) {
5520     Diag(TemplateLoc, diag::err_explicit_instantiation_nontemplate_type)
5521       << Context.getTypeDeclType(Record);
5522     Diag(Record->getLocation(), diag::note_nontemplate_decl_here);
5523     return true;
5524   }
5525
5526   // C++0x [temp.explicit]p2:
5527   //   If the explicit instantiation is for a class or member class, the
5528   //   elaborated-type-specifier in the declaration shall include a
5529   //   simple-template-id.
5530   //
5531   // C++98 has the same restriction, just worded differently.
5532   if (!ScopeSpecifierHasTemplateId(SS))
5533     Diag(TemplateLoc, diag::ext_explicit_instantiation_without_qualified_id)
5534       << Record << SS.getRange();
5535
5536   // C++0x [temp.explicit]p2:
5537   //   There are two forms of explicit instantiation: an explicit instantiation
5538   //   definition and an explicit instantiation declaration. An explicit
5539   //   instantiation declaration begins with the extern keyword. [...]
5540   TemplateSpecializationKind TSK
5541     = ExternLoc.isInvalid()? TSK_ExplicitInstantiationDefinition
5542                            : TSK_ExplicitInstantiationDeclaration;
5543
5544   // C++0x [temp.explicit]p2:
5545   //   [...] An explicit instantiation shall appear in an enclosing
5546   //   namespace of its template. [...]
5547   //
5548   // This is C++ DR 275.
5549   CheckExplicitInstantiationScope(*this, Record, NameLoc, true);
5550
5551   // Verify that it is okay to explicitly instantiate here.
5552   CXXRecordDecl *PrevDecl
5553     = cast_or_null<CXXRecordDecl>(Record->getPreviousDeclaration());
5554   if (!PrevDecl && Record->getDefinition())
5555     PrevDecl = Record;
5556   if (PrevDecl) {
5557     MemberSpecializationInfo *MSInfo = PrevDecl->getMemberSpecializationInfo();
5558     bool HasNoEffect = false;
5559     assert(MSInfo && "No member specialization information?");
5560     if (CheckSpecializationInstantiationRedecl(TemplateLoc, TSK,
5561                                                PrevDecl,
5562                                         MSInfo->getTemplateSpecializationKind(),
5563                                              MSInfo->getPointOfInstantiation(),
5564                                                HasNoEffect))
5565       return true;
5566     if (HasNoEffect)
5567       return TagD;
5568   }
5569
5570   CXXRecordDecl *RecordDef
5571     = cast_or_null<CXXRecordDecl>(Record->getDefinition());
5572   if (!RecordDef) {
5573     // C++ [temp.explicit]p3:
5574     //   A definition of a member class of a class template shall be in scope
5575     //   at the point of an explicit instantiation of the member class.
5576     CXXRecordDecl *Def
5577       = cast_or_null<CXXRecordDecl>(Pattern->getDefinition());
5578     if (!Def) {
5579       Diag(TemplateLoc, diag::err_explicit_instantiation_undefined_member)
5580         << 0 << Record->getDeclName() << Record->getDeclContext();
5581       Diag(Pattern->getLocation(), diag::note_forward_declaration)
5582         << Pattern;
5583       return true;
5584     } else {
5585       if (InstantiateClass(NameLoc, Record, Def,
5586                            getTemplateInstantiationArgs(Record),
5587                            TSK))
5588         return true;
5589
5590       RecordDef = cast_or_null<CXXRecordDecl>(Record->getDefinition());
5591       if (!RecordDef)
5592         return true;
5593     }
5594   }
5595
5596   // Instantiate all of the members of the class.
5597   InstantiateClassMembers(NameLoc, RecordDef,
5598                           getTemplateInstantiationArgs(Record), TSK);
5599
5600   if (TSK == TSK_ExplicitInstantiationDefinition)
5601     MarkVTableUsed(NameLoc, RecordDef, true);
5602
5603   // FIXME: We don't have any representation for explicit instantiations of
5604   // member classes. Such a representation is not needed for compilation, but it
5605   // should be available for clients that want to see all of the declarations in
5606   // the source code.
5607   return TagD;
5608 }
5609
5610 DeclResult Sema::ActOnExplicitInstantiation(Scope *S,
5611                                             SourceLocation ExternLoc,
5612                                             SourceLocation TemplateLoc,
5613                                             Declarator &D) {
5614   // Explicit instantiations always require a name.
5615   // TODO: check if/when DNInfo should replace Name.
5616   DeclarationNameInfo NameInfo = GetNameForDeclarator(D);
5617   DeclarationName Name = NameInfo.getName();
5618   if (!Name) {
5619     if (!D.isInvalidType())
5620       Diag(D.getDeclSpec().getSourceRange().getBegin(),
5621            diag::err_explicit_instantiation_requires_name)
5622         << D.getDeclSpec().getSourceRange()
5623         << D.getSourceRange();
5624
5625     return true;
5626   }
5627
5628   // The scope passed in may not be a decl scope.  Zip up the scope tree until
5629   // we find one that is.
5630   while ((S->getFlags() & Scope::DeclScope) == 0 ||
5631          (S->getFlags() & Scope::TemplateParamScope) != 0)
5632     S = S->getParent();
5633
5634   // Determine the type of the declaration.
5635   TypeSourceInfo *T = GetTypeForDeclarator(D, S);
5636   QualType R = T->getType();
5637   if (R.isNull())
5638     return true;
5639
5640   if (D.getDeclSpec().getStorageClassSpec() == DeclSpec::SCS_typedef) {
5641     // Cannot explicitly instantiate a typedef.
5642     Diag(D.getIdentifierLoc(), diag::err_explicit_instantiation_of_typedef)
5643       << Name;
5644     return true;
5645   }
5646
5647   // C++0x [temp.explicit]p1:
5648   //   [...] An explicit instantiation of a function template shall not use the
5649   //   inline or constexpr specifiers.
5650   // Presumably, this also applies to member functions of class templates as
5651   // well.
5652   if (D.getDeclSpec().isInlineSpecified() && getLangOptions().CPlusPlus0x)
5653     Diag(D.getDeclSpec().getInlineSpecLoc(),
5654          diag::err_explicit_instantiation_inline)
5655       <<FixItHint::CreateRemoval(D.getDeclSpec().getInlineSpecLoc());
5656
5657   // FIXME: check for constexpr specifier.
5658
5659   // C++0x [temp.explicit]p2:
5660   //   There are two forms of explicit instantiation: an explicit instantiation
5661   //   definition and an explicit instantiation declaration. An explicit
5662   //   instantiation declaration begins with the extern keyword. [...]
5663   TemplateSpecializationKind TSK
5664     = ExternLoc.isInvalid()? TSK_ExplicitInstantiationDefinition
5665                            : TSK_ExplicitInstantiationDeclaration;
5666
5667   LookupResult Previous(*this, NameInfo, LookupOrdinaryName);
5668   LookupParsedName(Previous, S, &D.getCXXScopeSpec());
5669
5670   if (!R->isFunctionType()) {
5671     // C++ [temp.explicit]p1:
5672     //   A [...] static data member of a class template can be explicitly
5673     //   instantiated from the member definition associated with its class
5674     //   template.
5675     if (Previous.isAmbiguous())
5676       return true;
5677
5678     VarDecl *Prev = Previous.getAsSingle<VarDecl>();
5679     if (!Prev || !Prev->isStaticDataMember()) {
5680       // We expect to see a data data member here.
5681       Diag(D.getIdentifierLoc(), diag::err_explicit_instantiation_not_known)
5682         << Name;
5683       for (LookupResult::iterator P = Previous.begin(), PEnd = Previous.end();
5684            P != PEnd; ++P)
5685         Diag((*P)->getLocation(), diag::note_explicit_instantiation_here);
5686       return true;
5687     }
5688
5689     if (!Prev->getInstantiatedFromStaticDataMember()) {
5690       // FIXME: Check for explicit specialization?
5691       Diag(D.getIdentifierLoc(),
5692            diag::err_explicit_instantiation_data_member_not_instantiated)
5693         << Prev;
5694       Diag(Prev->getLocation(), diag::note_explicit_instantiation_here);
5695       // FIXME: Can we provide a note showing where this was declared?
5696       return true;
5697     }
5698
5699     // C++0x [temp.explicit]p2:
5700     //   If the explicit instantiation is for a member function, a member class
5701     //   or a static data member of a class template specialization, the name of
5702     //   the class template specialization in the qualified-id for the member
5703     //   name shall be a simple-template-id.
5704     //
5705     // C++98 has the same restriction, just worded differently.
5706     if (!ScopeSpecifierHasTemplateId(D.getCXXScopeSpec()))
5707       Diag(D.getIdentifierLoc(),
5708            diag::ext_explicit_instantiation_without_qualified_id)
5709         << Prev << D.getCXXScopeSpec().getRange();
5710
5711     // Check the scope of this explicit instantiation.
5712     CheckExplicitInstantiationScope(*this, Prev, D.getIdentifierLoc(), true);
5713
5714     // Verify that it is okay to explicitly instantiate here.
5715     MemberSpecializationInfo *MSInfo = Prev->getMemberSpecializationInfo();
5716     assert(MSInfo && "Missing static data member specialization info?");
5717     bool HasNoEffect = false;
5718     if (CheckSpecializationInstantiationRedecl(D.getIdentifierLoc(), TSK, Prev,
5719                                         MSInfo->getTemplateSpecializationKind(),
5720                                               MSInfo->getPointOfInstantiation(),
5721                                                HasNoEffect))
5722       return true;
5723     if (HasNoEffect)
5724       return (Decl*) 0;
5725
5726     // Instantiate static data member.
5727     Prev->setTemplateSpecializationKind(TSK, D.getIdentifierLoc());
5728     if (TSK == TSK_ExplicitInstantiationDefinition)
5729       InstantiateStaticDataMemberDefinition(D.getIdentifierLoc(), Prev);
5730
5731     // FIXME: Create an ExplicitInstantiation node?
5732     return (Decl*) 0;
5733   }
5734
5735   // If the declarator is a template-id, translate the parser's template
5736   // argument list into our AST format.
5737   bool HasExplicitTemplateArgs = false;
5738   TemplateArgumentListInfo TemplateArgs;
5739   if (D.getName().getKind() == UnqualifiedId::IK_TemplateId) {
5740     TemplateIdAnnotation *TemplateId = D.getName().TemplateId;
5741     TemplateArgs.setLAngleLoc(TemplateId->LAngleLoc);
5742     TemplateArgs.setRAngleLoc(TemplateId->RAngleLoc);
5743     ASTTemplateArgsPtr TemplateArgsPtr(*this,
5744                                        TemplateId->getTemplateArgs(),
5745                                        TemplateId->NumArgs);
5746     translateTemplateArguments(TemplateArgsPtr, TemplateArgs);
5747     HasExplicitTemplateArgs = true;
5748     TemplateArgsPtr.release();
5749   }
5750
5751   // C++ [temp.explicit]p1:
5752   //   A [...] function [...] can be explicitly instantiated from its template.
5753   //   A member function [...] of a class template can be explicitly
5754   //  instantiated from the member definition associated with its class
5755   //  template.
5756   UnresolvedSet<8> Matches;
5757   for (LookupResult::iterator P = Previous.begin(), PEnd = Previous.end();
5758        P != PEnd; ++P) {
5759     NamedDecl *Prev = *P;
5760     if (!HasExplicitTemplateArgs) {
5761       if (CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Prev)) {
5762         if (Context.hasSameUnqualifiedType(Method->getType(), R)) {
5763           Matches.clear();
5764
5765           Matches.addDecl(Method, P.getAccess());
5766           if (Method->getTemplateSpecializationKind() == TSK_Undeclared)
5767             break;
5768         }
5769       }
5770     }
5771
5772     FunctionTemplateDecl *FunTmpl = dyn_cast<FunctionTemplateDecl>(Prev);
5773     if (!FunTmpl)
5774       continue;
5775
5776     TemplateDeductionInfo Info(Context, D.getIdentifierLoc());
5777     FunctionDecl *Specialization = 0;
5778     if (TemplateDeductionResult TDK
5779           = DeduceTemplateArguments(FunTmpl,
5780                                (HasExplicitTemplateArgs ? &TemplateArgs : 0),
5781                                     R, Specialization, Info)) {
5782       // FIXME: Keep track of almost-matches?
5783       (void)TDK;
5784       continue;
5785     }
5786
5787     Matches.addDecl(Specialization, P.getAccess());
5788   }
5789
5790   // Find the most specialized function template specialization.
5791   UnresolvedSetIterator Result
5792     = getMostSpecialized(Matches.begin(), Matches.end(), TPOC_Other, 0,
5793                          D.getIdentifierLoc(),
5794                      PDiag(diag::err_explicit_instantiation_not_known) << Name,
5795                      PDiag(diag::err_explicit_instantiation_ambiguous) << Name,
5796                          PDiag(diag::note_explicit_instantiation_candidate));
5797
5798   if (Result == Matches.end())
5799     return true;
5800
5801   // Ignore access control bits, we don't need them for redeclaration checking.
5802   FunctionDecl *Specialization = cast<FunctionDecl>(*Result);
5803
5804   if (Specialization->getTemplateSpecializationKind() == TSK_Undeclared) {
5805     Diag(D.getIdentifierLoc(),
5806          diag::err_explicit_instantiation_member_function_not_instantiated)
5807       << Specialization
5808       << (Specialization->getTemplateSpecializationKind() ==
5809           TSK_ExplicitSpecialization);
5810     Diag(Specialization->getLocation(), diag::note_explicit_instantiation_here);
5811     return true;
5812   }
5813
5814   FunctionDecl *PrevDecl = Specialization->getPreviousDeclaration();
5815   if (!PrevDecl && Specialization->isThisDeclarationADefinition())
5816     PrevDecl = Specialization;
5817
5818   if (PrevDecl) {
5819     bool HasNoEffect = false;
5820     if (CheckSpecializationInstantiationRedecl(D.getIdentifierLoc(), TSK,
5821                                                PrevDecl,
5822                                      PrevDecl->getTemplateSpecializationKind(),
5823                                           PrevDecl->getPointOfInstantiation(),
5824                                                HasNoEffect))
5825       return true;
5826
5827     // FIXME: We may still want to build some representation of this
5828     // explicit specialization.
5829     if (HasNoEffect)
5830       return (Decl*) 0;
5831   }
5832
5833   Specialization->setTemplateSpecializationKind(TSK, D.getIdentifierLoc());
5834
5835   if (TSK == TSK_ExplicitInstantiationDefinition)
5836     InstantiateFunctionDefinition(D.getIdentifierLoc(), Specialization);
5837
5838   // C++0x [temp.explicit]p2:
5839   //   If the explicit instantiation is for a member function, a member class
5840   //   or a static data member of a class template specialization, the name of
5841   //   the class template specialization in the qualified-id for the member
5842   //   name shall be a simple-template-id.
5843   //
5844   // C++98 has the same restriction, just worded differently.
5845   FunctionTemplateDecl *FunTmpl = Specialization->getPrimaryTemplate();
5846   if (D.getName().getKind() != UnqualifiedId::IK_TemplateId && !FunTmpl &&
5847       D.getCXXScopeSpec().isSet() &&
5848       !ScopeSpecifierHasTemplateId(D.getCXXScopeSpec()))
5849     Diag(D.getIdentifierLoc(),
5850          diag::ext_explicit_instantiation_without_qualified_id)
5851     << Specialization << D.getCXXScopeSpec().getRange();
5852
5853   CheckExplicitInstantiationScope(*this,
5854                    FunTmpl? (NamedDecl *)FunTmpl
5855                           : Specialization->getInstantiatedFromMemberFunction(),
5856                                   D.getIdentifierLoc(),
5857                                   D.getCXXScopeSpec().isSet());
5858
5859   // FIXME: Create some kind of ExplicitInstantiationDecl here.
5860   return (Decl*) 0;
5861 }
5862
5863 TypeResult
5864 Sema::ActOnDependentTag(Scope *S, unsigned TagSpec, TagUseKind TUK,
5865                         const CXXScopeSpec &SS, IdentifierInfo *Name,
5866                         SourceLocation TagLoc, SourceLocation NameLoc) {
5867   // This has to hold, because SS is expected to be defined.
5868   assert(Name && "Expected a name in a dependent tag");
5869
5870   NestedNameSpecifier *NNS
5871     = static_cast<NestedNameSpecifier *>(SS.getScopeRep());
5872   if (!NNS)
5873     return true;
5874
5875   TagTypeKind Kind = TypeWithKeyword::getTagTypeKindForTypeSpec(TagSpec);
5876
5877   if (TUK == TUK_Declaration || TUK == TUK_Definition) {
5878     Diag(NameLoc, diag::err_dependent_tag_decl)
5879       << (TUK == TUK_Definition) << Kind << SS.getRange();
5880     return true;
5881   }
5882
5883   ElaboratedTypeKeyword Kwd = TypeWithKeyword::getKeywordForTagTypeKind(Kind);
5884   return ParsedType::make(Context.getDependentNameType(Kwd, NNS, Name));
5885 }
5886
5887 TypeResult
5888 Sema::ActOnTypenameType(Scope *S, SourceLocation TypenameLoc,
5889                         const CXXScopeSpec &SS, const IdentifierInfo &II,
5890                         SourceLocation IdLoc) {
5891   NestedNameSpecifier *NNS
5892     = static_cast<NestedNameSpecifier *>(SS.getScopeRep());
5893   if (!NNS)
5894     return true;
5895
5896   if (TypenameLoc.isValid() && S && !S->getTemplateParamParent() &&
5897       !getLangOptions().CPlusPlus0x)
5898     Diag(TypenameLoc, diag::ext_typename_outside_of_template)
5899       << FixItHint::CreateRemoval(TypenameLoc);
5900
5901   QualType T = CheckTypenameType(ETK_Typename, NNS, II,
5902                                  TypenameLoc, SS.getRange(), IdLoc);
5903   if (T.isNull())
5904     return true;
5905
5906   TypeSourceInfo *TSI = Context.CreateTypeSourceInfo(T);
5907   if (isa<DependentNameType>(T)) {
5908     DependentNameTypeLoc TL = cast<DependentNameTypeLoc>(TSI->getTypeLoc());
5909     TL.setKeywordLoc(TypenameLoc);
5910     TL.setQualifierRange(SS.getRange());
5911     TL.setNameLoc(IdLoc);
5912   } else {
5913     ElaboratedTypeLoc TL = cast<ElaboratedTypeLoc>(TSI->getTypeLoc());
5914     TL.setKeywordLoc(TypenameLoc);
5915     TL.setQualifierRange(SS.getRange());
5916     cast<TypeSpecTypeLoc>(TL.getNamedTypeLoc()).setNameLoc(IdLoc);
5917   }
5918
5919   return CreateParsedType(T, TSI);
5920 }
5921
5922 TypeResult
5923 Sema::ActOnTypenameType(Scope *S, SourceLocation TypenameLoc,
5924                         const CXXScopeSpec &SS, SourceLocation TemplateLoc,
5925                         ParsedType Ty) {
5926   if (TypenameLoc.isValid() && S && !S->getTemplateParamParent() &&
5927       !getLangOptions().CPlusPlus0x)
5928     Diag(TypenameLoc, diag::ext_typename_outside_of_template)
5929       << FixItHint::CreateRemoval(TypenameLoc);
5930
5931   TypeSourceInfo *InnerTSI = 0;
5932   QualType T = GetTypeFromParser(Ty, &InnerTSI);
5933
5934   assert(isa<TemplateSpecializationType>(T) &&
5935          "Expected a template specialization type");
5936
5937   if (computeDeclContext(SS, false)) {
5938     // If we can compute a declaration context, then the "typename"
5939     // keyword was superfluous. Just build an ElaboratedType to keep
5940     // track of the nested-name-specifier.
5941
5942     // Push the inner type, preserving its source locations if possible.
5943     TypeLocBuilder Builder;
5944     if (InnerTSI)
5945       Builder.pushFullCopy(InnerTSI->getTypeLoc());
5946     else
5947       Builder.push<TemplateSpecializationTypeLoc>(T).initialize(Context,
5948                                                                 TemplateLoc);
5949
5950     /* Note: NNS already embedded in template specialization type T. */
5951     T = Context.getElaboratedType(ETK_Typename, /*NNS=*/0, T);
5952     ElaboratedTypeLoc TL = Builder.push<ElaboratedTypeLoc>(T);
5953     TL.setKeywordLoc(TypenameLoc);
5954     TL.setQualifierRange(SS.getRange());
5955
5956     TypeSourceInfo *TSI = Builder.getTypeSourceInfo(Context, T);
5957     return CreateParsedType(T, TSI);
5958   }
5959
5960   // TODO: it's really silly that we make a template specialization
5961   // type earlier only to drop it again here.
5962   const TemplateSpecializationType *TST = cast<TemplateSpecializationType>(T);
5963   DependentTemplateName *DTN =
5964     TST->getTemplateName().getAsDependentTemplateName();
5965   assert(DTN && "dependent template has non-dependent name?");
5966   assert(DTN->getQualifier()
5967          == static_cast<NestedNameSpecifier*>(SS.getScopeRep()));
5968   T = Context.getDependentTemplateSpecializationType(ETK_Typename,
5969                                                      DTN->getQualifier(),
5970                                                      DTN->getIdentifier(),
5971                                                      TST->getNumArgs(),
5972                                                      TST->getArgs());
5973   TypeSourceInfo *TSI = Context.CreateTypeSourceInfo(T);
5974   DependentTemplateSpecializationTypeLoc TL =
5975     cast<DependentTemplateSpecializationTypeLoc>(TSI->getTypeLoc());
5976   if (InnerTSI) {
5977     TemplateSpecializationTypeLoc TSTL =
5978       cast<TemplateSpecializationTypeLoc>(InnerTSI->getTypeLoc());
5979     TL.setLAngleLoc(TSTL.getLAngleLoc());
5980     TL.setRAngleLoc(TSTL.getRAngleLoc());
5981     for (unsigned I = 0, E = TST->getNumArgs(); I != E; ++I)
5982       TL.setArgLocInfo(I, TSTL.getArgLocInfo(I));
5983   } else {
5984     // FIXME: Poor source-location information here.
5985     TL.initializeLocal(Context, TemplateLoc);
5986   }
5987   TL.setKeywordLoc(TypenameLoc);
5988   TL.setQualifierRange(SS.getRange());
5989   return CreateParsedType(T, TSI);
5990 }
5991
5992 /// \brief Build the type that describes a C++ typename specifier,
5993 /// e.g., "typename T::type".
5994 QualType
5995 Sema::CheckTypenameType(ElaboratedTypeKeyword Keyword,
5996                         NestedNameSpecifier *NNS, const IdentifierInfo &II,
5997                         SourceLocation KeywordLoc, SourceRange NNSRange,
5998                         SourceLocation IILoc) {
5999   CXXScopeSpec SS;
6000   SS.setScopeRep(NNS);
6001   SS.setRange(NNSRange);
6002
6003   DeclContext *Ctx = computeDeclContext(SS);
6004   if (!Ctx) {
6005     // If the nested-name-specifier is dependent and couldn't be
6006     // resolved to a type, build a typename type.
6007     assert(NNS->isDependent());
6008     return Context.getDependentNameType(Keyword, NNS, &II);
6009   }
6010
6011   // If the nested-name-specifier refers to the current instantiation,
6012   // the "typename" keyword itself is superfluous. In C++03, the
6013   // program is actually ill-formed. However, DR 382 (in C++0x CD1)
6014   // allows such extraneous "typename" keywords, and we retroactively
6015   // apply this DR to C++03 code with only a warning. In any case we continue.
6016
6017   if (RequireCompleteDeclContext(SS, Ctx))
6018     return QualType();
6019
6020   DeclarationName Name(&II);
6021   LookupResult Result(*this, Name, IILoc, LookupOrdinaryName);
6022   LookupQualifiedName(Result, Ctx);
6023   unsigned DiagID = 0;
6024   Decl *Referenced = 0;
6025   switch (Result.getResultKind()) {
6026   case LookupResult::NotFound:
6027     DiagID = diag::err_typename_nested_not_found;
6028     break;
6029
6030   case LookupResult::FoundUnresolvedValue: {
6031     // We found a using declaration that is a value. Most likely, the using
6032     // declaration itself is meant to have the 'typename' keyword.
6033     SourceRange FullRange(KeywordLoc.isValid() ? KeywordLoc : NNSRange.getBegin(),
6034                           IILoc);
6035     Diag(IILoc, diag::err_typename_refers_to_using_value_decl)
6036       << Name << Ctx << FullRange;
6037     if (UnresolvedUsingValueDecl *Using
6038           = dyn_cast<UnresolvedUsingValueDecl>(Result.getRepresentativeDecl())){
6039       SourceLocation Loc = Using->getTargetNestedNameRange().getBegin();
6040       Diag(Loc, diag::note_using_value_decl_missing_typename)
6041         << FixItHint::CreateInsertion(Loc, "typename ");
6042     }
6043   }
6044   // Fall through to create a dependent typename type, from which we can recover
6045   // better.
6046
6047   case LookupResult::NotFoundInCurrentInstantiation:
6048     // Okay, it's a member of an unknown instantiation.
6049     return Context.getDependentNameType(Keyword, NNS, &II);
6050
6051   case LookupResult::Found:
6052     if (TypeDecl *Type = dyn_cast<TypeDecl>(Result.getFoundDecl())) {
6053       // We found a type. Build an ElaboratedType, since the
6054       // typename-specifier was just sugar.
6055       return Context.getElaboratedType(ETK_Typename, NNS,
6056                                        Context.getTypeDeclType(Type));
6057     }
6058
6059     DiagID = diag::err_typename_nested_not_type;
6060     Referenced = Result.getFoundDecl();
6061     break;
6062
6063
6064     llvm_unreachable("unresolved using decl in non-dependent context");
6065     return QualType();
6066
6067   case LookupResult::FoundOverloaded:
6068     DiagID = diag::err_typename_nested_not_type;
6069     Referenced = *Result.begin();
6070     break;
6071
6072   case LookupResult::Ambiguous:
6073     return QualType();
6074   }
6075
6076   // If we get here, it's because name lookup did not find a
6077   // type. Emit an appropriate diagnostic and return an error.
6078   SourceRange FullRange(KeywordLoc.isValid() ? KeywordLoc : NNSRange.getBegin(),
6079                         IILoc);
6080   Diag(IILoc, DiagID) << FullRange << Name << Ctx;
6081   if (Referenced)
6082     Diag(Referenced->getLocation(), diag::note_typename_refers_here)
6083       << Name;
6084   return QualType();
6085 }
6086
6087 namespace {
6088   // See Sema::RebuildTypeInCurrentInstantiation
6089   class CurrentInstantiationRebuilder
6090     : public TreeTransform<CurrentInstantiationRebuilder> {
6091     SourceLocation Loc;
6092     DeclarationName Entity;
6093
6094   public:
6095     typedef TreeTransform<CurrentInstantiationRebuilder> inherited;
6096
6097     CurrentInstantiationRebuilder(Sema &SemaRef,
6098                                   SourceLocation Loc,
6099                                   DeclarationName Entity)
6100     : TreeTransform<CurrentInstantiationRebuilder>(SemaRef),
6101       Loc(Loc), Entity(Entity) { }
6102
6103     /// \brief Determine whether the given type \p T has already been
6104     /// transformed.
6105     ///
6106     /// For the purposes of type reconstruction, a type has already been
6107     /// transformed if it is NULL or if it is not dependent.
6108     bool AlreadyTransformed(QualType T) {
6109       return T.isNull() || !T->isDependentType();
6110     }
6111
6112     /// \brief Returns the location of the entity whose type is being
6113     /// rebuilt.
6114     SourceLocation getBaseLocation() { return Loc; }
6115
6116     /// \brief Returns the name of the entity whose type is being rebuilt.
6117     DeclarationName getBaseEntity() { return Entity; }
6118
6119     /// \brief Sets the "base" location and entity when that
6120     /// information is known based on another transformation.
6121     void setBase(SourceLocation Loc, DeclarationName Entity) {
6122       this->Loc = Loc;
6123       this->Entity = Entity;
6124     }
6125   };
6126 }
6127
6128 /// \brief Rebuilds a type within the context of the current instantiation.
6129 ///
6130 /// The type \p T is part of the type of an out-of-line member definition of
6131 /// a class template (or class template partial specialization) that was parsed
6132 /// and constructed before we entered the scope of the class template (or
6133 /// partial specialization thereof). This routine will rebuild that type now
6134 /// that we have entered the declarator's scope, which may produce different
6135 /// canonical types, e.g.,
6136 ///
6137 /// \code
6138 /// template<typename T>
6139 /// struct X {
6140 ///   typedef T* pointer;
6141 ///   pointer data();
6142 /// };
6143 ///
6144 /// template<typename T>
6145 /// typename X<T>::pointer X<T>::data() { ... }
6146 /// \endcode
6147 ///
6148 /// Here, the type "typename X<T>::pointer" will be created as a DependentNameType,
6149 /// since we do not know that we can look into X<T> when we parsed the type.
6150 /// This function will rebuild the type, performing the lookup of "pointer"
6151 /// in X<T> and returning an ElaboratedType whose canonical type is the same
6152 /// as the canonical type of T*, allowing the return types of the out-of-line
6153 /// definition and the declaration to match.
6154 TypeSourceInfo *Sema::RebuildTypeInCurrentInstantiation(TypeSourceInfo *T,
6155                                                         SourceLocation Loc,
6156                                                         DeclarationName Name) {
6157   if (!T || !T->getType()->isDependentType())
6158     return T;
6159
6160   CurrentInstantiationRebuilder Rebuilder(*this, Loc, Name);
6161   return Rebuilder.TransformType(T);
6162 }
6163
6164 ExprResult Sema::RebuildExprInCurrentInstantiation(Expr *E) {
6165   CurrentInstantiationRebuilder Rebuilder(*this, E->getExprLoc(),
6166                                           DeclarationName());
6167   return Rebuilder.TransformExpr(E);
6168 }
6169
6170 bool Sema::RebuildNestedNameSpecifierInCurrentInstantiation(CXXScopeSpec &SS) {
6171   if (SS.isInvalid()) return true;
6172
6173   NestedNameSpecifier *NNS = static_cast<NestedNameSpecifier*>(SS.getScopeRep());
6174   CurrentInstantiationRebuilder Rebuilder(*this, SS.getRange().getBegin(),
6175                                           DeclarationName());
6176   NestedNameSpecifier *Rebuilt =
6177     Rebuilder.TransformNestedNameSpecifier(NNS, SS.getRange());
6178   if (!Rebuilt) return true;
6179
6180   SS.setScopeRep(Rebuilt);
6181   return false;
6182 }
6183
6184 /// \brief Produces a formatted string that describes the binding of
6185 /// template parameters to template arguments.
6186 std::string
6187 Sema::getTemplateArgumentBindingsText(const TemplateParameterList *Params,
6188                                       const TemplateArgumentList &Args) {
6189   return getTemplateArgumentBindingsText(Params, Args.data(), Args.size());
6190 }
6191
6192 std::string
6193 Sema::getTemplateArgumentBindingsText(const TemplateParameterList *Params,
6194                                       const TemplateArgument *Args,
6195                                       unsigned NumArgs) {
6196   llvm::SmallString<128> Str;
6197   llvm::raw_svector_ostream Out(Str);
6198
6199   if (!Params || Params->size() == 0 || NumArgs == 0)
6200     return std::string();
6201
6202   for (unsigned I = 0, N = Params->size(); I != N; ++I) {
6203     if (I >= NumArgs)
6204       break;
6205
6206     if (I == 0)
6207       Out << "[with ";
6208     else
6209       Out << ", ";
6210
6211     if (const IdentifierInfo *Id = Params->getParam(I)->getIdentifier()) {
6212       Out << Id->getName();
6213     } else {
6214       Out << '$' << I;
6215     }
6216
6217     Out << " = ";
6218     Args[I].print(Context.PrintingPolicy, Out);
6219   }
6220
6221   Out << ']';
6222   return Out.str();
6223 }