SemaTemplate.cpp revision 6f37b58716e89420c13ac067fe605c3b6d5821d0 
1//===------- SemaTemplate.cpp - Semantic Analysis for C++ Templates -------===/
2
3//
4//                     The LLVM Compiler Infrastructure
5//
6// This file is distributed under the University of Illinois Open Source
7// License. See LICENSE.TXT for details.
8//+//===----------------------------------------------------------------------===/
9
10//
11//  This file implements semantic analysis for C++ templates.
12//+//===----------------------------------------------------------------------===/
13
14#include "Sema.h"
15#include "clang/AST/ASTContext.h"
16#include "clang/AST/Expr.h"
17#include "clang/AST/DeclTemplate.h"
18#include "clang/Parse/DeclSpec.h"
19#include "clang/Basic/LangOptions.h"
20
21using namespace clang;
22
23/// isTemplateName - Determines whether the identifier II is a
24/// template name in the current scope, and returns the template
25/// declaration if II names a template. An optional CXXScope can be
26/// passed to indicate the C++ scope in which the identifier will be
27/// found.
28Sema::TemplateNameKind Sema::isTemplateName(IdentifierInfo &II, Scope *S,
29                                            DeclTy *&Template,
30                                            const CXXScopeSpec *SS) {
31  NamedDecl *IIDecl = LookupParsedName(S, SS, &II, LookupOrdinaryName);
32
33  if (IIDecl) {
34    if (isa<TemplateDecl>(IIDecl)) {
35      Template = IIDecl;
36      if (isa<FunctionTemplateDecl>(IIDecl))
37        return TNK_Function_template;
38      else if (isa<ClassTemplateDecl>(IIDecl))
39        return TNK_Class_template;
40      else if (isa<TemplateTemplateParmDecl>(IIDecl))
41        return TNK_Template_template_parm;
42      else
43        assert(false && "Unknown TemplateDecl");
44    }
45
46    // FIXME: What follows is a gross hack.
47    if (FunctionDecl *FD = dyn_cast<FunctionDecl>(IIDecl)) {
48      if (FD->getType()->isDependentType()) {
49        Template = FD;
50        return TNK_Function_template;
51      }
52    } else if (OverloadedFunctionDecl *Ovl
53                 = dyn_cast<OverloadedFunctionDecl>(IIDecl)) {
54      for (OverloadedFunctionDecl::function_iterator F = Ovl->function_begin(),
55                                                  FEnd = Ovl->function_end();
56           F != FEnd; ++F) {
57        if ((*F)->getType()->isDependentType()) {
58          Template = Ovl;
59          return TNK_Function_template;
60        }
61      }
62    }
63  }
64  return TNK_Non_template;
65}
66
67/// DiagnoseTemplateParameterShadow - Produce a diagnostic complaining
68/// that the template parameter 'PrevDecl' is being shadowed by a new
69/// declaration at location Loc. Returns true to indicate that this is
70/// an error, and false otherwise.
71bool Sema::DiagnoseTemplateParameterShadow(SourceLocation Loc, Decl *PrevDecl) {
72  assert(PrevDecl->isTemplateParameter() && "Not a template parameter");
73
74  // Microsoft Visual C++ permits template parameters to be shadowed.
75  if (getLangOptions().Microsoft)
76    return false;
77
78  // C++ [temp.local]p4:
79  //   A template-parameter shall not be redeclared within its
80  //   scope (including nested scopes).
81  Diag(Loc, diag::err_template_param_shadow)
82    << cast<NamedDecl>(PrevDecl)->getDeclName();
83  Diag(PrevDecl->getLocation(), diag::note_template_param_here);
84  return true;
85}
86
87/// AdjustDeclForTemplates - If the given decl happens to be a template, reset
88/// the parameter D to reference the templated declaration and return a pointer
89/// to the template declaration. Otherwise, do nothing to D and return null.
90TemplateDecl *Sema::AdjustDeclIfTemplate(DeclTy *&D)
91{
92  if(TemplateDecl *Temp = dyn_cast<TemplateDecl>(static_cast<Decl*>(D))) {
93    D = Temp->getTemplatedDecl();
94    return Temp;
95  }
96  return 0;
97}
98
99/// ActOnTypeParameter - Called when a C++ template type parameter
100/// (e.g., "typename T") has been parsed. Typename specifies whether
101/// the keyword "typename" was used to declare the type parameter
102/// (otherwise, "class" was used), and KeyLoc is the location of the
103/// "class" or "typename" keyword. ParamName is the name of the
104/// parameter (NULL indicates an unnamed template parameter) and
105/// ParamName is the location of the parameter name (if any).
106/// If the type parameter has a default argument, it will be added
107/// later via ActOnTypeParameterDefault.
108Sema::DeclTy *Sema::ActOnTypeParameter(Scope *S, bool Typename,
109				       SourceLocation KeyLoc,
110				       IdentifierInfo *ParamName,
111				       SourceLocation ParamNameLoc,
112                                       unsigned Depth, unsigned Position) {
113  assert(S->isTemplateParamScope() &&
114	 "Template type parameter not in template parameter scope!");
115  bool Invalid = false;
116
117  if (ParamName) {
118    NamedDecl *PrevDecl = LookupName(S, ParamName, LookupTagName);
119    if (PrevDecl && PrevDecl->isTemplateParameter())
120      Invalid = Invalid || DiagnoseTemplateParameterShadow(ParamNameLoc,
121							   PrevDecl);
122  }
123
124  SourceLocation Loc = ParamNameLoc;
125  if (!ParamName)
126    Loc = KeyLoc;
127
128  TemplateTypeParmDecl *Param
129    = TemplateTypeParmDecl::Create(Context, CurContext, Loc,
130                                   Depth, Position, ParamName, Typename);
131  if (Invalid)
132    Param->setInvalidDecl();
133
134  if (ParamName) {
135    // Add the template parameter into the current scope.
136    S->AddDecl(Param);
137    IdResolver.AddDecl(Param);
138  }
139
140  return Param;
141}
142
143/// ActOnNonTypeTemplateParameter - Called when a C++ non-type
144/// template parameter (e.g., "int Size" in "template<int Size>
145/// class Array") has been parsed. S is the current scope and D is
146/// the parsed declarator.
147Sema::DeclTy *Sema::ActOnNonTypeTemplateParameter(Scope *S, Declarator &D,
148                                                  unsigned Depth,
149                                                  unsigned Position) {
150  QualType T = GetTypeForDeclarator(D, S);
151
152  assert(S->isTemplateParamScope() &&
153         "Non-type template parameter not in template parameter scope!");
154  bool Invalid = false;
155
156  IdentifierInfo *ParamName = D.getIdentifier();
157  if (ParamName) {
158    NamedDecl *PrevDecl = LookupName(S, ParamName, LookupTagName);
159    if (PrevDecl && PrevDecl->isTemplateParameter())
160      Invalid = Invalid || DiagnoseTemplateParameterShadow(D.getIdentifierLoc(),
161                                                           PrevDecl);
162  }
163
164  NonTypeTemplateParmDecl *Param
165    = NonTypeTemplateParmDecl::Create(Context, CurContext, D.getIdentifierLoc(),
166                                      Depth, Position, ParamName, T);
167  if (Invalid)
168    Param->setInvalidDecl();
169
170  if (D.getIdentifier()) {
171    // Add the template parameter into the current scope.
172    S->AddDecl(Param);
173    IdResolver.AddDecl(Param);
174  }
175  return Param;
176}
177
178
179/// ActOnTemplateTemplateParameter - Called when a C++ template template
180/// parameter (e.g. T in template <template <typename> class T> class array)
181/// has been parsed. S is the current scope.
182Sema::DeclTy *Sema::ActOnTemplateTemplateParameter(Scope* S,
183                                                   SourceLocation TmpLoc,
184                                                   TemplateParamsTy *Params,
185                                                   IdentifierInfo *Name,
186                                                   SourceLocation NameLoc,
187                                                   unsigned Depth,
188                                                   unsigned Position)
189{
190  assert(S->isTemplateParamScope() &&
191         "Template template parameter not in template parameter scope!");
192
193  // Construct the parameter object.
194  TemplateTemplateParmDecl *Param =
195    TemplateTemplateParmDecl::Create(Context, CurContext, TmpLoc, Depth,
196                                     Position, Name,
197                                     (TemplateParameterList*)Params);
198
199  // Make sure the parameter is valid.
200  // FIXME: Decl object is not currently invalidated anywhere so this doesn't
201  // do anything yet. However, if the template parameter list or (eventual)
202  // default value is ever invalidated, that will propagate here.
203  bool Invalid = false;
204  if (Invalid) {
205    Param->setInvalidDecl();
206  }
207
208  // If the tt-param has a name, then link the identifier into the scope
209  // and lookup mechanisms.
210  if (Name) {
211    S->AddDecl(Param);
212    IdResolver.AddDecl(Param);
213  }
214
215  return Param;
216}
217
218/// ActOnTemplateParameterList - Builds a TemplateParameterList that
219/// contains the template parameters in Params/NumParams.
220Sema::TemplateParamsTy *
221Sema::ActOnTemplateParameterList(unsigned Depth,
222                                 SourceLocation ExportLoc,
223                                 SourceLocation TemplateLoc,
224                                 SourceLocation LAngleLoc,
225                                 DeclTy **Params, unsigned NumParams,
226                                 SourceLocation RAngleLoc) {
227  if (ExportLoc.isValid())
228    Diag(ExportLoc, diag::note_template_export_unsupported);
229
230  return TemplateParameterList::Create(Context, TemplateLoc, LAngleLoc,
231                                       (Decl**)Params, NumParams, RAngleLoc);
232}
233
234Sema::DeclTy *
235Sema::ActOnClassTemplate(Scope *S, unsigned TagSpec, TagKind TK,
236                         SourceLocation KWLoc, const CXXScopeSpec &SS,
237                         IdentifierInfo *Name, SourceLocation NameLoc,
238                         AttributeList *Attr,
239                         MultiTemplateParamsArg TemplateParameterLists) {
240  assert(TemplateParameterLists.size() > 0 && "No template parameter lists?");
241  assert(TK != TK_Reference && "Can only declare or define class templates");
242
243  // Check that we can declare a template here.
244  if (CheckTemplateDeclScope(S, TemplateParameterLists))
245    return 0;
246
247  TagDecl::TagKind Kind;
248  switch (TagSpec) {
249  default: assert(0 && "Unknown tag type!");
250  case DeclSpec::TST_struct: Kind = TagDecl::TK_struct; break;
251  case DeclSpec::TST_union:  Kind = TagDecl::TK_union; break;
252  case DeclSpec::TST_class:  Kind = TagDecl::TK_class; break;
253  }
254
255  // There is no such thing as an unnamed class template.
256  if (!Name) {
257    Diag(KWLoc, diag::err_template_unnamed_class);
258    return 0;
259  }
260
261  // Find any previous declaration with this name.
262  LookupResult Previous = LookupParsedName(S, &SS, Name, LookupOrdinaryName,
263                                           true);
264  assert(!Previous.isAmbiguous() && "Ambiguity in class template redecl?");
265  NamedDecl *PrevDecl = 0;
266  if (Previous.begin() != Previous.end())
267    PrevDecl = *Previous.begin();
268
269  DeclContext *SemanticContext = CurContext;
270  if (SS.isNotEmpty() && !SS.isInvalid()) {
271    SemanticContext = static_cast<DeclContext*>(SS.getScopeRep());
272
273    // FIXME: need to match up several levels of template parameter
274    // lists here.
275  }
276
277  // FIXME: member templates!
278  TemplateParameterList *TemplateParams
279    = static_cast<TemplateParameterList *>(*TemplateParameterLists.release());
280
281  // If there is a previous declaration with the same name, check
282  // whether this is a valid redeclaration.
283  ClassTemplateDecl *PrevClassTemplate
284    = dyn_cast_or_null<ClassTemplateDecl>(PrevDecl);
285  if (PrevClassTemplate) {
286    // Ensure that the template parameter lists are compatible.
287    if (!TemplateParameterListsAreEqual(TemplateParams,
288                                   PrevClassTemplate->getTemplateParameters(),
289                                        /*Complain=*/true))
290      return 0;
291
292    // C++ [temp.class]p4:
293    //   In a redeclaration, partial specialization, explicit
294    //   specialization or explicit instantiation of a class template,
295    //   the class-key shall agree in kind with the original class
296    //   template declaration (7.1.5.3).
297    RecordDecl *PrevRecordDecl = PrevClassTemplate->getTemplatedDecl();
298    if (PrevRecordDecl->getTagKind() != Kind) {
299      Diag(KWLoc, diag::err_use_with_wrong_tag) << Name;
300      Diag(PrevRecordDecl->getLocation(), diag::note_previous_use);
301      return 0;
302    }
303
304
305    // Check for redefinition of this class template.
306    if (TK == TK_Definition) {
307      if (TagDecl *Def = PrevRecordDecl->getDefinition(Context)) {
308        Diag(NameLoc, diag::err_redefinition) << Name;
309        Diag(Def->getLocation(), diag::note_previous_definition);
310        // FIXME: Would it make sense to try to "forget" the previous
311        // definition, as part of error recovery?
312        return 0;
313      }
314    }
315  } else if (PrevDecl && PrevDecl->isTemplateParameter()) {
316    // Maybe we will complain about the shadowed template parameter.
317    DiagnoseTemplateParameterShadow(NameLoc, PrevDecl);
318    // Just pretend that we didn't see the previous declaration.
319    PrevDecl = 0;
320  } else if (PrevDecl) {
321    // C++ [temp]p5:
322    //   A class template shall not have the same name as any other
323    //   template, class, function, object, enumeration, enumerator,
324    //   namespace, or type in the same scope (3.3), except as specified
325    //   in (14.5.4).
326    Diag(NameLoc, diag::err_redefinition_different_kind) << Name;
327    Diag(PrevDecl->getLocation(), diag::note_previous_definition);
328    return 0;
329  }
330
331  // If we had a scope specifier, we better have a previous template
332  // declaration!
333
334  TagDecl *NewClass =
335    CXXRecordDecl::Create(Context, Kind, SemanticContext, NameLoc, Name,
336                          PrevClassTemplate?
337                            PrevClassTemplate->getTemplatedDecl() : 0);
338
339  ClassTemplateDecl *NewTemplate
340    = ClassTemplateDecl::Create(Context, SemanticContext, NameLoc,
341                                DeclarationName(Name), TemplateParams,
342                                NewClass);
343
344  // Set the lexical context of these templates
345  NewClass->setLexicalDeclContext(CurContext);
346  NewTemplate->setLexicalDeclContext(CurContext);
347
348  if (TK == TK_Definition)
349    NewClass->startDefinition();
350
351  if (Attr)
352    ProcessDeclAttributeList(NewClass, Attr);
353
354  PushOnScopeChains(NewTemplate, S);
355
356  return NewTemplate;
357}
358
359Action::TypeTy *
360Sema::ActOnClassTemplateSpecialization(DeclTy *TemplateD,
361                                       SourceLocation LAngleLoc,
362                                       ASTTemplateArgsPtr TemplateArgs,
363                                       SourceLocation RAngleLoc,
364                                       const CXXScopeSpec *SS) {
365  TemplateDecl *Template = cast<TemplateDecl>(static_cast<Decl *>(TemplateD));
366
367  // Yes, all class template specializations are just silly sugar for
368  // 'int'. Gotta problem wit dat?
369  QualType Result
370    = Context.getClassTemplateSpecializationType(Template,
371                                                 TemplateArgs.size(),
372                    reinterpret_cast<uintptr_t *>(TemplateArgs.getArgs()),
373                                                 TemplateArgs.getArgIsType(),
374                                                 Context.IntTy);
375  TemplateArgs.release();
376  return Result.getAsOpaquePtr();
377}
378
379/// \brief Determine whether the given template parameter lists are
380/// equivalent.
381///
382/// \param New  The new template parameter list, typically written in the
383/// source code as part of a new template declaration.
384///
385/// \param Old  The old template parameter list, typically found via
386/// name lookup of the template declared with this template parameter
387/// list.
388///
389/// \param Complain  If true, this routine will produce a diagnostic if
390/// the template parameter lists are not equivalent.
391///
392/// \returns True if the template parameter lists are equal, false
393/// otherwise.
394bool
395Sema::TemplateParameterListsAreEqual(TemplateParameterList *New,
396                                     TemplateParameterList *Old,
397                                     bool Complain,
398                                     bool IsTemplateTemplateParm) {
399  if (Old->size() != New->size()) {
400    if (Complain) {
401      Diag(New->getTemplateLoc(), diag::err_template_param_list_different_arity)
402        << (New->size() > Old->size())
403        << IsTemplateTemplateParm
404        << SourceRange(New->getTemplateLoc(), New->getRAngleLoc());
405      Diag(Old->getTemplateLoc(), diag::note_template_prev_declaration)
406        << IsTemplateTemplateParm
407        << SourceRange(Old->getTemplateLoc(), Old->getRAngleLoc());
408    }
409
410    return false;
411  }
412
413  for (TemplateParameterList::iterator OldParm = Old->begin(),
414         OldParmEnd = Old->end(), NewParm = New->begin();
415       OldParm != OldParmEnd; ++OldParm, ++NewParm) {
416    if ((*OldParm)->getKind() != (*NewParm)->getKind()) {
417      Diag((*NewParm)->getLocation(), diag::err_template_param_different_kind)
418        << IsTemplateTemplateParm;
419      Diag((*OldParm)->getLocation(), diag::note_template_prev_declaration)
420        << IsTemplateTemplateParm;
421      return false;
422    }
423
424    if (isa<TemplateTypeParmDecl>(*OldParm)) {
425      // Okay; all template type parameters are equivalent (since we
426      // know we're at the same depth/level).
427#ifndef NDEBUG
428      QualType OldParmType
429        = Context.getTypeDeclType(cast<TemplateTypeParmDecl>(*OldParm));
430      QualType NewParmType
431        = Context.getTypeDeclType(cast<TemplateTypeParmDecl>(*NewParm));
432      assert(Context.getCanonicalType(OldParmType) ==
433             Context.getCanonicalType(NewParmType) &&
434             "type parameter mismatch?");
435#endif
436    } else if (NonTypeTemplateParmDecl *OldNTTP
437                 = dyn_cast<NonTypeTemplateParmDecl>(*OldParm)) {
438      // The types of non-type template parameters must agree.
439      NonTypeTemplateParmDecl *NewNTTP
440        = cast<NonTypeTemplateParmDecl>(*NewParm);
441      if (Context.getCanonicalType(OldNTTP->getType()) !=
442            Context.getCanonicalType(NewNTTP->getType())) {
443        if (Complain) {
444          Diag(NewNTTP->getLocation(),
445               diag::err_template_nontype_parm_different_type)
446            << NewNTTP->getType()
447            << IsTemplateTemplateParm;
448          Diag(OldNTTP->getLocation(),
449               diag::note_template_nontype_parm_prev_declaration)
450            << OldNTTP->getType();
451        }
452        return false;
453      }
454    } else {
455      // The template parameter lists of template template
456      // parameters must agree.
457      // FIXME: Could we perform a faster "type" comparison here?
458      assert(isa<TemplateTemplateParmDecl>(*OldParm) &&
459             "Only template template parameters handled here");
460      TemplateTemplateParmDecl *OldTTP
461        = cast<TemplateTemplateParmDecl>(*OldParm);
462      TemplateTemplateParmDecl *NewTTP
463        = cast<TemplateTemplateParmDecl>(*NewParm);
464      if (!TemplateParameterListsAreEqual(NewTTP->getTemplateParameters(),
465                                          OldTTP->getTemplateParameters(),
466                                          Complain,
467                                          /*IsTemplateTemplateParm=*/true))
468        return false;
469    }
470  }
471
472  return true;
473}
474
475/// \brief Check whether a template can be declared within this scope.
476///
477/// If the template declaration is valid in this scope, returns
478/// false. Otherwise, issues a diagnostic and returns true.
479bool
480Sema::CheckTemplateDeclScope(Scope *S,
481                             MultiTemplateParamsArg &TemplateParameterLists) {
482  assert(TemplateParameterLists.size() > 0 && "Not a template");
483
484  // Find the nearest enclosing declaration scope.
485  while ((S->getFlags() & Scope::DeclScope) == 0 ||
486         (S->getFlags() & Scope::TemplateParamScope) != 0)
487    S = S->getParent();
488
489  TemplateParameterList *TemplateParams =
490    static_cast<TemplateParameterList*>(*TemplateParameterLists.get());
491  SourceLocation TemplateLoc = TemplateParams->getTemplateLoc();
492  SourceRange TemplateRange
493    = SourceRange(TemplateLoc, TemplateParams->getRAngleLoc());
494
495  // C++ [temp]p2:
496  //   A template-declaration can appear only as a namespace scope or
497  //   class scope declaration.
498  DeclContext *Ctx = static_cast<DeclContext *>(S->getEntity());
499  while (Ctx && isa<LinkageSpecDecl>(Ctx)) {
500    if (cast<LinkageSpecDecl>(Ctx)->getLanguage() != LinkageSpecDecl::lang_cxx)
501      return Diag(TemplateLoc, diag::err_template_linkage)
502        << TemplateRange;
503
504    Ctx = Ctx->getParent();
505  }
506
507  if (Ctx && (Ctx->isFileContext() || Ctx->isRecord()))
508    return false;
509
510  return Diag(TemplateLoc, diag::err_template_outside_namespace_or_class_scope)
511    << TemplateRange;
512}
513