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