Template.h revision 612409ece080e814f79e06772c690d603f45fbd6 
1//===------- SemaTemplate.h - C++ Templates ---------------------*- C++ -*-===/
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 provides types used in the semantic analysis of C++ templates.
10//
11//===----------------------------------------------------------------------===/
12#ifndef LLVM_CLANG_SEMA_TEMPLATE_H
13#define LLVM_CLANG_SEMA_TEMPLATE_H
14
15#include "clang/AST/DeclTemplate.h"
16#include "clang/AST/DeclVisitor.h"
17#include "llvm/ADT/SmallVector.h"
18#include <cassert>
19#include <utility>
20
21namespace clang {
22  /// \brief Data structure that captures multiple levels of template argument
23  /// lists for use in template instantiation.
24  ///
25  /// Multiple levels of template arguments occur when instantiating the
26  /// definitions of member templates. For example:
27  ///
28  /// \code
29  /// template<typename T>
30  /// struct X {
31  ///   template<T Value>
32  ///   struct Y {
33  ///     void f();
34  ///   };
35  /// };
36  /// \endcode
37  ///
38  /// When instantiating X<int>::Y<17>::f, the multi-level template argument
39  /// list will contain a template argument list (int) at depth 0 and a
40  /// template argument list (17) at depth 1.
41  class MultiLevelTemplateArgumentList {
42  public:
43    typedef std::pair<const TemplateArgument *, unsigned> ArgList;
44
45  private:
46    /// \brief The template argument lists, stored from the innermost template
47    /// argument list (first) to the outermost template argument list (last).
48    SmallVector<ArgList, 4> TemplateArgumentLists;
49
50  public:
51    /// \brief Construct an empty set of template argument lists.
52    MultiLevelTemplateArgumentList() { }
53
54    /// \brief Construct a single-level template argument list.
55    explicit
56    MultiLevelTemplateArgumentList(const TemplateArgumentList &TemplateArgs) {
57      addOuterTemplateArguments(&TemplateArgs);
58    }
59
60    /// \brief Determine the number of levels in this template argument
61    /// list.
62    unsigned getNumLevels() const { return TemplateArgumentLists.size(); }
63
64    /// \brief Retrieve the template argument at a given depth and index.
65    const TemplateArgument &operator()(unsigned Depth, unsigned Index) const {
66      assert(Depth < TemplateArgumentLists.size());
67      assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].second);
68      return TemplateArgumentLists[getNumLevels() - Depth - 1].first[Index];
69    }
70
71    /// \brief Determine whether there is a non-NULL template argument at the
72    /// given depth and index.
73    ///
74    /// There must exist a template argument list at the given depth.
75    bool hasTemplateArgument(unsigned Depth, unsigned Index) const {
76      assert(Depth < TemplateArgumentLists.size());
77
78      if (Index >= TemplateArgumentLists[getNumLevels() - Depth - 1].second)
79        return false;
80
81      return !(*this)(Depth, Index).isNull();
82    }
83
84    /// \brief Clear out a specific template argument.
85    void setArgument(unsigned Depth, unsigned Index,
86                     TemplateArgument Arg) {
87      assert(Depth < TemplateArgumentLists.size());
88      assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].second);
89      const_cast<TemplateArgument&>(
90                TemplateArgumentLists[getNumLevels() - Depth - 1].first[Index])
91        = Arg;
92    }
93
94    /// \brief Add a new outermost level to the multi-level template argument
95    /// list.
96    void addOuterTemplateArguments(const TemplateArgumentList *TemplateArgs) {
97      TemplateArgumentLists.push_back(ArgList(TemplateArgs->data(),
98                                              TemplateArgs->size()));
99    }
100
101    /// \brief Add a new outmost level to the multi-level template argument
102    /// list.
103    void addOuterTemplateArguments(const TemplateArgument *Args,
104                                   unsigned NumArgs) {
105      TemplateArgumentLists.push_back(ArgList(Args, NumArgs));
106    }
107
108    /// \brief Retrieve the innermost template argument list.
109    const ArgList &getInnermost() const {
110      return TemplateArgumentLists.front();
111    }
112  };
113
114  /// \brief The context in which partial ordering of function templates occurs.
115  enum TPOC {
116    /// \brief Partial ordering of function templates for a function call.
117    TPOC_Call,
118    /// \brief Partial ordering of function templates for a call to a
119    /// conversion function.
120    TPOC_Conversion,
121    /// \brief Partial ordering of function templates in other contexts, e.g.,
122    /// taking the address of a function template or matching a function
123    /// template specialization to a function template.
124    TPOC_Other
125  };
126
127  // This is lame but unavoidable in a world without forward
128  // declarations of enums.  The alternatives are to either pollute
129  // Sema.h (by including this file) or sacrifice type safety (by
130  // making Sema.h declare things as enums).
131  class TemplatePartialOrderingContext {
132    TPOC Value;
133  public:
134    TemplatePartialOrderingContext(TPOC Value) : Value(Value) {}
135    operator TPOC() const { return Value; }
136  };
137
138  /// \brief Captures a template argument whose value has been deduced
139  /// via c++ template argument deduction.
140  class DeducedTemplateArgument : public TemplateArgument {
141    /// \brief For a non-type template argument, whether the value was
142    /// deduced from an array bound.
143    bool DeducedFromArrayBound;
144
145  public:
146    DeducedTemplateArgument()
147      : TemplateArgument(), DeducedFromArrayBound(false) { }
148
149    DeducedTemplateArgument(const TemplateArgument &Arg,
150                            bool DeducedFromArrayBound = false)
151      : TemplateArgument(Arg), DeducedFromArrayBound(DeducedFromArrayBound) { }
152
153    /// \brief Construct an integral non-type template argument that
154    /// has been deduced, possibly from an array bound.
155    DeducedTemplateArgument(ASTContext &Ctx,
156                            const llvm::APSInt &Value,
157                            QualType ValueType,
158                            bool DeducedFromArrayBound)
159      : TemplateArgument(Ctx, Value, ValueType),
160        DeducedFromArrayBound(DeducedFromArrayBound) { }
161
162    /// \brief For a non-type template argument, determine whether the
163    /// template argument was deduced from an array bound.
164    bool wasDeducedFromArrayBound() const { return DeducedFromArrayBound; }
165
166    /// \brief Specify whether the given non-type template argument
167    /// was deduced from an array bound.
168    void setDeducedFromArrayBound(bool Deduced) {
169      DeducedFromArrayBound = Deduced;
170    }
171  };
172
173  /// \brief A stack-allocated class that identifies which local
174  /// variable declaration instantiations are present in this scope.
175  ///
176  /// A new instance of this class type will be created whenever we
177  /// instantiate a new function declaration, which will have its own
178  /// set of parameter declarations.
179  class LocalInstantiationScope {
180  public:
181    /// \brief A set of declarations.
182    typedef SmallVector<Decl *, 4> DeclArgumentPack;
183
184  private:
185    /// \brief Reference to the semantic analysis that is performing
186    /// this template instantiation.
187    Sema &SemaRef;
188
189    typedef llvm::DenseMap<const Decl *,
190                           llvm::PointerUnion<Decl *, DeclArgumentPack *> >
191      LocalDeclsMap;
192
193    /// \brief A mapping from local declarations that occur
194    /// within a template to their instantiations.
195    ///
196    /// This mapping is used during instantiation to keep track of,
197    /// e.g., function parameter and variable declarations. For example,
198    /// given:
199    ///
200    /// \code
201    ///   template<typename T> T add(T x, T y) { return x + y; }
202    /// \endcode
203    ///
204    /// when we instantiate add<int>, we will introduce a mapping from
205    /// the ParmVarDecl for 'x' that occurs in the template to the
206    /// instantiated ParmVarDecl for 'x'.
207    ///
208    /// For a parameter pack, the local instantiation scope may contain a
209    /// set of instantiated parameters. This is stored as a DeclArgumentPack
210    /// pointer.
211    LocalDeclsMap LocalDecls;
212
213    /// \brief The set of argument packs we've allocated.
214    SmallVector<DeclArgumentPack *, 1> ArgumentPacks;
215
216    /// \brief The outer scope, which contains local variable
217    /// definitions from some other instantiation (that may not be
218    /// relevant to this particular scope).
219    LocalInstantiationScope *Outer;
220
221    /// \brief Whether we have already exited this scope.
222    bool Exited;
223
224    /// \brief Whether to combine this scope with the outer scope, such that
225    /// lookup will search our outer scope.
226    bool CombineWithOuterScope;
227
228    /// \brief If non-NULL, the template parameter pack that has been
229    /// partially substituted per C++0x [temp.arg.explicit]p9.
230    NamedDecl *PartiallySubstitutedPack;
231
232    /// \brief If \c PartiallySubstitutedPack is non-null, the set of
233    /// explicitly-specified template arguments in that pack.
234    const TemplateArgument *ArgsInPartiallySubstitutedPack;
235
236    /// \brief If \c PartiallySubstitutedPack, the number of
237    /// explicitly-specified template arguments in
238    /// ArgsInPartiallySubstitutedPack.
239    unsigned NumArgsInPartiallySubstitutedPack;
240
241    // This class is non-copyable
242    LocalInstantiationScope(const LocalInstantiationScope &);
243    LocalInstantiationScope &operator=(const LocalInstantiationScope &);
244
245  public:
246    LocalInstantiationScope(Sema &SemaRef, bool CombineWithOuterScope = false)
247      : SemaRef(SemaRef), Outer(SemaRef.CurrentInstantiationScope),
248        Exited(false), CombineWithOuterScope(CombineWithOuterScope),
249        PartiallySubstitutedPack(0)
250    {
251      SemaRef.CurrentInstantiationScope = this;
252    }
253
254    ~LocalInstantiationScope() {
255      Exit();
256    }
257
258    const Sema &getSema() const { return SemaRef; }
259
260    /// \brief Exit this local instantiation scope early.
261    void Exit() {
262      if (Exited)
263        return;
264
265      for (unsigned I = 0, N = ArgumentPacks.size(); I != N; ++I)
266        delete ArgumentPacks[I];
267
268      SemaRef.CurrentInstantiationScope = Outer;
269      Exited = true;
270    }
271
272    /// \brief Clone this scope, and all outer scopes, down to the given
273    /// outermost scope.
274    LocalInstantiationScope *cloneScopes(LocalInstantiationScope *Outermost) {
275      if (this == Outermost) return this;
276      LocalInstantiationScope *newScope =
277        new LocalInstantiationScope(SemaRef, CombineWithOuterScope);
278
279      newScope->Outer = 0;
280      if (Outer)
281        newScope->Outer = Outer->cloneScopes(Outermost);
282
283      newScope->PartiallySubstitutedPack = PartiallySubstitutedPack;
284      newScope->ArgsInPartiallySubstitutedPack = ArgsInPartiallySubstitutedPack;
285      newScope->NumArgsInPartiallySubstitutedPack =
286        NumArgsInPartiallySubstitutedPack;
287
288      for (LocalDeclsMap::iterator I = LocalDecls.begin(), E = LocalDecls.end();
289           I != E; ++I) {
290        const Decl *D = I->first;
291        llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored =
292          newScope->LocalDecls[D];
293        if (I->second.is<Decl *>()) {
294          Stored = I->second.get<Decl *>();
295        } else {
296          DeclArgumentPack *OldPack = I->second.get<DeclArgumentPack *>();
297          DeclArgumentPack *NewPack = new DeclArgumentPack(*OldPack);
298          Stored = NewPack;
299          newScope->ArgumentPacks.push_back(NewPack);
300        }
301      }
302      return newScope;
303    }
304
305    /// \brief deletes the given scope, and all otuer scopes, down to the
306    /// given outermost scope.
307    static void deleteScopes(LocalInstantiationScope *Scope,
308                             LocalInstantiationScope *Outermost) {
309      while (Scope && Scope != Outermost) {
310        LocalInstantiationScope *Out = Scope->Outer;
311        delete Scope;
312        Scope = Out;
313      }
314    }
315
316    /// \brief Find the instantiation of the declaration D within the current
317    /// instantiation scope.
318    ///
319    /// \param D The declaration whose instantiation we are searching for.
320    ///
321    /// \returns A pointer to the declaration or argument pack of declarations
322    /// to which the declaration \c D is instantiataed, if found. Otherwise,
323    /// returns NULL.
324    llvm::PointerUnion<Decl *, DeclArgumentPack *> *
325    findInstantiationOf(const Decl *D);
326
327    void InstantiatedLocal(const Decl *D, Decl *Inst);
328    void InstantiatedLocalPackArg(const Decl *D, Decl *Inst);
329    void MakeInstantiatedLocalArgPack(const Decl *D);
330
331    /// \brief Note that the given parameter pack has been partially substituted
332    /// via explicit specification of template arguments
333    /// (C++0x [temp.arg.explicit]p9).
334    ///
335    /// \param Pack The parameter pack, which will always be a template
336    /// parameter pack.
337    ///
338    /// \param ExplicitArgs The explicitly-specified template arguments provided
339    /// for this parameter pack.
340    ///
341    /// \param NumExplicitArgs The number of explicitly-specified template
342    /// arguments provided for this parameter pack.
343    void SetPartiallySubstitutedPack(NamedDecl *Pack,
344                                     const TemplateArgument *ExplicitArgs,
345                                     unsigned NumExplicitArgs);
346
347    /// \brief Retrieve the partially-substitued template parameter pack.
348    ///
349    /// If there is no partially-substituted parameter pack, returns NULL.
350    NamedDecl *getPartiallySubstitutedPack(
351                                      const TemplateArgument **ExplicitArgs = 0,
352                                           unsigned *NumExplicitArgs = 0) const;
353  };
354
355  class TemplateDeclInstantiator
356    : public DeclVisitor<TemplateDeclInstantiator, Decl *>
357  {
358    Sema &SemaRef;
359    Sema::ArgumentPackSubstitutionIndexRAII SubstIndex;
360    DeclContext *Owner;
361    const MultiLevelTemplateArgumentList &TemplateArgs;
362    Sema::LateInstantiatedAttrVec* LateAttrs;
363    LocalInstantiationScope *StartingScope;
364
365    /// \brief A list of out-of-line class template partial
366    /// specializations that will need to be instantiated after the
367    /// enclosing class's instantiation is complete.
368    SmallVector<std::pair<ClassTemplateDecl *,
369                                ClassTemplatePartialSpecializationDecl *>, 4>
370      OutOfLinePartialSpecs;
371
372  public:
373    TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
374                             const MultiLevelTemplateArgumentList &TemplateArgs)
375      : SemaRef(SemaRef),
376        SubstIndex(SemaRef, SemaRef.ArgumentPackSubstitutionIndex),
377        Owner(Owner), TemplateArgs(TemplateArgs), LateAttrs(0), StartingScope(0)
378    { }
379
380    // FIXME: Once we get closer to completion, replace these manually-written
381    // declarations with automatically-generated ones from
382    // clang/AST/DeclNodes.inc.
383    Decl *VisitTranslationUnitDecl(TranslationUnitDecl *D);
384    Decl *VisitLabelDecl(LabelDecl *D);
385    Decl *VisitNamespaceDecl(NamespaceDecl *D);
386    Decl *VisitNamespaceAliasDecl(NamespaceAliasDecl *D);
387    Decl *VisitTypedefDecl(TypedefDecl *D);
388    Decl *VisitTypeAliasDecl(TypeAliasDecl *D);
389    Decl *VisitTypeAliasTemplateDecl(TypeAliasTemplateDecl *D);
390    Decl *VisitVarDecl(VarDecl *D);
391    Decl *VisitAccessSpecDecl(AccessSpecDecl *D);
392    Decl *VisitFieldDecl(FieldDecl *D);
393    Decl *VisitIndirectFieldDecl(IndirectFieldDecl *D);
394    Decl *VisitStaticAssertDecl(StaticAssertDecl *D);
395    Decl *VisitEnumDecl(EnumDecl *D);
396    Decl *VisitEnumConstantDecl(EnumConstantDecl *D);
397    Decl *VisitFriendDecl(FriendDecl *D);
398    Decl *VisitFunctionDecl(FunctionDecl *D,
399                            TemplateParameterList *TemplateParams = 0);
400    Decl *VisitCXXRecordDecl(CXXRecordDecl *D);
401    Decl *VisitCXXMethodDecl(CXXMethodDecl *D,
402                             TemplateParameterList *TemplateParams = 0,
403                             bool IsClassScopeSpecialization = false);
404    Decl *VisitCXXConstructorDecl(CXXConstructorDecl *D);
405    Decl *VisitCXXDestructorDecl(CXXDestructorDecl *D);
406    Decl *VisitCXXConversionDecl(CXXConversionDecl *D);
407    ParmVarDecl *VisitParmVarDecl(ParmVarDecl *D);
408    Decl *VisitClassTemplateDecl(ClassTemplateDecl *D);
409    Decl *VisitClassTemplatePartialSpecializationDecl(
410                                    ClassTemplatePartialSpecializationDecl *D);
411    Decl *VisitFunctionTemplateDecl(FunctionTemplateDecl *D);
412    Decl *VisitTemplateTypeParmDecl(TemplateTypeParmDecl *D);
413    Decl *VisitNonTypeTemplateParmDecl(NonTypeTemplateParmDecl *D);
414    Decl *VisitTemplateTemplateParmDecl(TemplateTemplateParmDecl *D);
415    Decl *VisitUsingDirectiveDecl(UsingDirectiveDecl *D);
416    Decl *VisitUsingDecl(UsingDecl *D);
417    Decl *VisitUsingShadowDecl(UsingShadowDecl *D);
418    Decl *VisitUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *D);
419    Decl *VisitUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *D);
420    Decl *VisitClassScopeFunctionSpecializationDecl(
421                                      ClassScopeFunctionSpecializationDecl *D);
422
423    // Base case. FIXME: Remove once we can instantiate everything.
424    Decl *VisitDecl(Decl *D) {
425      unsigned DiagID = SemaRef.getDiagnostics().getCustomDiagID(
426                                                   DiagnosticsEngine::Error,
427                                                   "cannot instantiate %0 yet");
428      SemaRef.Diag(D->getLocation(), DiagID)
429        << D->getDeclKindName();
430
431      return 0;
432    }
433
434    // Enable late instantiation of attributes.  Late instantiated attributes
435    // will be stored in LA.
436    void enableLateAttributeInstantiation(Sema::LateInstantiatedAttrVec *LA) {
437      LateAttrs = LA;
438      StartingScope = SemaRef.CurrentInstantiationScope;
439    }
440
441    // Disable late instantiation of attributes.
442    void disableLateAttributeInstantiation() {
443      LateAttrs = 0;
444      StartingScope = 0;
445    }
446
447    LocalInstantiationScope *getStartingScope() const { return StartingScope; }
448
449    typedef
450      SmallVectorImpl<std::pair<ClassTemplateDecl *,
451                                     ClassTemplatePartialSpecializationDecl *> >
452        ::iterator
453      delayed_partial_spec_iterator;
454
455    /// \brief Return an iterator to the beginning of the set of
456    /// "delayed" partial specializations, which must be passed to
457    /// InstantiateClassTemplatePartialSpecialization once the class
458    /// definition has been completed.
459    delayed_partial_spec_iterator delayed_partial_spec_begin() {
460      return OutOfLinePartialSpecs.begin();
461    }
462
463    /// \brief Return an iterator to the end of the set of
464    /// "delayed" partial specializations, which must be passed to
465    /// InstantiateClassTemplatePartialSpecialization once the class
466    /// definition has been completed.
467    delayed_partial_spec_iterator delayed_partial_spec_end() {
468      return OutOfLinePartialSpecs.end();
469    }
470
471    // Helper functions for instantiating methods.
472    TypeSourceInfo *SubstFunctionType(FunctionDecl *D,
473                             SmallVectorImpl<ParmVarDecl *> &Params);
474    bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
475    bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
476
477    TemplateParameterList *
478      SubstTemplateParams(TemplateParameterList *List);
479
480    bool SubstQualifier(const DeclaratorDecl *OldDecl,
481                        DeclaratorDecl *NewDecl);
482    bool SubstQualifier(const TagDecl *OldDecl,
483                        TagDecl *NewDecl);
484
485    Decl *InstantiateTypedefNameDecl(TypedefNameDecl *D, bool IsTypeAlias);
486    ClassTemplatePartialSpecializationDecl *
487    InstantiateClassTemplatePartialSpecialization(
488                                              ClassTemplateDecl *ClassTemplate,
489                           ClassTemplatePartialSpecializationDecl *PartialSpec);
490    void InstantiateEnumDefinition(EnumDecl *Enum, EnumDecl *Pattern);
491  };
492}
493
494#endif // LLVM_CLANG_SEMA_TEMPLATE_H
495