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