Template.h revision 12c9c00024a01819e3a70ef6d951d32efaeb9312 
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    llvm::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 Add a new outermost level to the multi-level template argument
85    /// list.
86    void addOuterTemplateArguments(const TemplateArgumentList *TemplateArgs) {
87      TemplateArgumentLists.push_back(ArgList(TemplateArgs->data(),
88                                              TemplateArgs->size()));
89    }
90
91    /// \brief Add a new outmost level to the multi-level template argument
92    /// list.
93    void addOuterTemplateArguments(const TemplateArgument *Args,
94                                   unsigned NumArgs) {
95      TemplateArgumentLists.push_back(ArgList(Args, NumArgs));
96    }
97
98    /// \brief Retrieve the innermost template argument list.
99    const ArgList &getInnermost() const {
100      return TemplateArgumentLists.front();
101    }
102  };
103
104  /// \brief The context in which partial ordering of function templates occurs.
105  enum TPOC {
106    /// \brief Partial ordering of function templates for a function call.
107    TPOC_Call,
108    /// \brief Partial ordering of function templates for a call to a
109    /// conversion function.
110    TPOC_Conversion,
111    /// \brief Partial ordering of function templates in other contexts, e.g.,
112    /// taking the address of a function template or matching a function
113    /// template specialization to a function template.
114    TPOC_Other
115  };
116
117  // This is lame but unavoidable in a world without forward
118  // declarations of enums.  The alternatives are to either pollute
119  // Sema.h (by including this file) or sacrifice type safety (by
120  // making Sema.h declare things as enums).
121  class TemplatePartialOrderingContext {
122    TPOC Value;
123  public:
124    TemplatePartialOrderingContext(TPOC Value) : Value(Value) {}
125    operator TPOC() const { return Value; }
126  };
127
128  /// \brief Captures a template argument whose value has been deduced
129  /// via c++ template argument deduction.
130  class DeducedTemplateArgument : public TemplateArgument {
131    /// \brief For a non-type template argument, whether the value was
132    /// deduced from an array bound.
133    bool DeducedFromArrayBound;
134
135  public:
136    DeducedTemplateArgument()
137      : TemplateArgument(), DeducedFromArrayBound(false) { }
138
139    DeducedTemplateArgument(const TemplateArgument &Arg,
140                            bool DeducedFromArrayBound = false)
141      : TemplateArgument(Arg), DeducedFromArrayBound(DeducedFromArrayBound) { }
142
143    /// \brief Construct an integral non-type template argument that
144    /// has been deduced, possible from an array bound.
145    DeducedTemplateArgument(const llvm::APSInt &Value,
146                            QualType ValueType,
147                            bool DeducedFromArrayBound)
148      : TemplateArgument(Value, ValueType),
149        DeducedFromArrayBound(DeducedFromArrayBound) { }
150
151    /// \brief For a non-type template argument, determine whether the
152    /// template argument was deduced from an array bound.
153    bool wasDeducedFromArrayBound() const { return DeducedFromArrayBound; }
154
155    /// \brief Specify whether the given non-type template argument
156    /// was deduced from an array bound.
157    void setDeducedFromArrayBound(bool Deduced) {
158      DeducedFromArrayBound = Deduced;
159    }
160  };
161
162  /// \brief A stack-allocated class that identifies which local
163  /// variable declaration instantiations are present in this scope.
164  ///
165  /// A new instance of this class type will be created whenever we
166  /// instantiate a new function declaration, which will have its own
167  /// set of parameter declarations.
168  class LocalInstantiationScope {
169  public:
170    /// \brief A set of declarations.
171    typedef llvm::SmallVector<Decl *, 4> DeclArgumentPack;
172
173  private:
174    /// \brief Reference to the semantic analysis that is performing
175    /// this template instantiation.
176    Sema &SemaRef;
177
178    typedef llvm::DenseMap<const Decl *,
179                           llvm::PointerUnion<Decl *, DeclArgumentPack *> >
180      LocalDeclsMap;
181
182    /// \brief A mapping from local declarations that occur
183    /// within a template to their instantiations.
184    ///
185    /// This mapping is used during instantiation to keep track of,
186    /// e.g., function parameter and variable declarations. For example,
187    /// given:
188    ///
189    /// \code
190    ///   template<typename T> T add(T x, T y) { return x + y; }
191    /// \endcode
192    ///
193    /// when we instantiate add<int>, we will introduce a mapping from
194    /// the ParmVarDecl for 'x' that occurs in the template to the
195    /// instantiated ParmVarDecl for 'x'.
196    ///
197    /// For a parameter pack, the local instantiation scope may contain a
198    /// set of instantiated parameters. This is stored as a DeclArgumentPack
199    /// pointer.
200    LocalDeclsMap LocalDecls;
201
202    /// \brief The set of argument packs we've allocated.
203    llvm::SmallVector<DeclArgumentPack *, 1> ArgumentPacks;
204
205    /// \brief The outer scope, which contains local variable
206    /// definitions from some other instantiation (that may not be
207    /// relevant to this particular scope).
208    LocalInstantiationScope *Outer;
209
210    /// \brief Whether we have already exited this scope.
211    bool Exited;
212
213    /// \brief Whether to combine this scope with the outer scope, such that
214    /// lookup will search our outer scope.
215    bool CombineWithOuterScope;
216
217    // This class is non-copyable
218    LocalInstantiationScope(const LocalInstantiationScope &);
219    LocalInstantiationScope &operator=(const LocalInstantiationScope &);
220
221  public:
222    LocalInstantiationScope(Sema &SemaRef, bool CombineWithOuterScope = false)
223      : SemaRef(SemaRef), Outer(SemaRef.CurrentInstantiationScope),
224        Exited(false), CombineWithOuterScope(CombineWithOuterScope)
225    {
226      SemaRef.CurrentInstantiationScope = this;
227    }
228
229    ~LocalInstantiationScope() {
230      Exit();
231    }
232
233    /// \brief Exit this local instantiation scope early.
234    void Exit() {
235      if (Exited)
236        return;
237
238      for (unsigned I = 0, N = ArgumentPacks.size(); I != N; ++I)
239        delete ArgumentPacks[I];
240
241      SemaRef.CurrentInstantiationScope = Outer;
242      Exited = true;
243    }
244
245    Decl *getInstantiationOf(const Decl *D);
246
247    /// \brief Find the instantiation of the declaration D within the current
248    /// instantiation scope.
249    ///
250    /// \param D The declaration whose instantiation we are searching for.
251    ///
252    /// \returns A pointer to the declaration or argument pack of declarations
253    /// to which the declaration \c D is instantiataed, if found. Otherwise,
254    /// returns NULL.
255    llvm::PointerUnion<Decl *, DeclArgumentPack *> *
256    findInstantiationOf(const Decl *D);
257
258    VarDecl *getInstantiationOf(const VarDecl *Var) {
259      return cast<VarDecl>(getInstantiationOf(cast<Decl>(Var)));
260    }
261
262    ParmVarDecl *getInstantiationOf(const ParmVarDecl *Var) {
263      return cast<ParmVarDecl>(getInstantiationOf(cast<Decl>(Var)));
264    }
265
266    NonTypeTemplateParmDecl *getInstantiationOf(
267                                          const NonTypeTemplateParmDecl *Var) {
268      return cast<NonTypeTemplateParmDecl>(getInstantiationOf(cast<Decl>(Var)));
269    }
270
271    void InstantiatedLocal(const Decl *D, Decl *Inst);
272    void InstantiatedLocalPackArg(const Decl *D, Decl *Inst);
273    void MakeInstantiatedLocalArgPack(const Decl *D);
274  };
275
276  class TemplateDeclInstantiator
277    : public DeclVisitor<TemplateDeclInstantiator, Decl *>
278  {
279    Sema &SemaRef;
280    Sema::ArgumentPackSubstitutionIndexRAII SubstIndex;
281    DeclContext *Owner;
282    const MultiLevelTemplateArgumentList &TemplateArgs;
283
284    /// \brief A list of out-of-line class template partial
285    /// specializations that will need to be instantiated after the
286    /// enclosing class's instantiation is complete.
287    llvm::SmallVector<std::pair<ClassTemplateDecl *,
288                                ClassTemplatePartialSpecializationDecl *>, 4>
289      OutOfLinePartialSpecs;
290
291  public:
292    TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
293                             const MultiLevelTemplateArgumentList &TemplateArgs)
294      : SemaRef(SemaRef), SubstIndex(SemaRef, -1), Owner(Owner),
295        TemplateArgs(TemplateArgs) { }
296
297    // FIXME: Once we get closer to completion, replace these manually-written
298    // declarations with automatically-generated ones from
299    // clang/AST/DeclNodes.inc.
300    Decl *VisitTranslationUnitDecl(TranslationUnitDecl *D);
301    Decl *VisitNamespaceDecl(NamespaceDecl *D);
302    Decl *VisitNamespaceAliasDecl(NamespaceAliasDecl *D);
303    Decl *VisitTypedefDecl(TypedefDecl *D);
304    Decl *VisitVarDecl(VarDecl *D);
305    Decl *VisitAccessSpecDecl(AccessSpecDecl *D);
306    Decl *VisitFieldDecl(FieldDecl *D);
307    Decl *VisitIndirectFieldDecl(IndirectFieldDecl *D);
308    Decl *VisitStaticAssertDecl(StaticAssertDecl *D);
309    Decl *VisitEnumDecl(EnumDecl *D);
310    Decl *VisitEnumConstantDecl(EnumConstantDecl *D);
311    Decl *VisitFriendDecl(FriendDecl *D);
312    Decl *VisitFunctionDecl(FunctionDecl *D,
313                            TemplateParameterList *TemplateParams = 0);
314    Decl *VisitCXXRecordDecl(CXXRecordDecl *D);
315    Decl *VisitCXXMethodDecl(CXXMethodDecl *D,
316                             TemplateParameterList *TemplateParams = 0);
317    Decl *VisitCXXConstructorDecl(CXXConstructorDecl *D);
318    Decl *VisitCXXDestructorDecl(CXXDestructorDecl *D);
319    Decl *VisitCXXConversionDecl(CXXConversionDecl *D);
320    ParmVarDecl *VisitParmVarDecl(ParmVarDecl *D);
321    Decl *VisitClassTemplateDecl(ClassTemplateDecl *D);
322    Decl *VisitClassTemplatePartialSpecializationDecl(
323                                    ClassTemplatePartialSpecializationDecl *D);
324    Decl *VisitFunctionTemplateDecl(FunctionTemplateDecl *D);
325    Decl *VisitTemplateTypeParmDecl(TemplateTypeParmDecl *D);
326    Decl *VisitNonTypeTemplateParmDecl(NonTypeTemplateParmDecl *D);
327    Decl *VisitTemplateTemplateParmDecl(TemplateTemplateParmDecl *D);
328    Decl *VisitUsingDirectiveDecl(UsingDirectiveDecl *D);
329    Decl *VisitUsingDecl(UsingDecl *D);
330    Decl *VisitUsingShadowDecl(UsingShadowDecl *D);
331    Decl *VisitUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *D);
332    Decl *VisitUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *D);
333
334    // Base case. FIXME: Remove once we can instantiate everything.
335    Decl *VisitDecl(Decl *D) {
336      unsigned DiagID = SemaRef.getDiagnostics().getCustomDiagID(
337                                                            Diagnostic::Error,
338                                                   "cannot instantiate %0 yet");
339      SemaRef.Diag(D->getLocation(), DiagID)
340        << D->getDeclKindName();
341
342      return 0;
343    }
344
345    typedef
346      llvm::SmallVectorImpl<std::pair<ClassTemplateDecl *,
347                                     ClassTemplatePartialSpecializationDecl *> >
348        ::iterator
349      delayed_partial_spec_iterator;
350
351    /// \brief Return an iterator to the beginning of the set of
352    /// "delayed" partial specializations, which must be passed to
353    /// InstantiateClassTemplatePartialSpecialization once the class
354    /// definition has been completed.
355    delayed_partial_spec_iterator delayed_partial_spec_begin() {
356      return OutOfLinePartialSpecs.begin();
357    }
358
359    /// \brief Return an iterator to the end of the set of
360    /// "delayed" partial specializations, which must be passed to
361    /// InstantiateClassTemplatePartialSpecialization once the class
362    /// definition has been completed.
363    delayed_partial_spec_iterator delayed_partial_spec_end() {
364      return OutOfLinePartialSpecs.end();
365    }
366
367    // Helper functions for instantiating methods.
368    TypeSourceInfo *SubstFunctionType(FunctionDecl *D,
369                             llvm::SmallVectorImpl<ParmVarDecl *> &Params);
370    bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
371    bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
372
373    TemplateParameterList *
374      SubstTemplateParams(TemplateParameterList *List);
375
376    bool SubstQualifier(const DeclaratorDecl *OldDecl,
377                        DeclaratorDecl *NewDecl);
378    bool SubstQualifier(const TagDecl *OldDecl,
379                        TagDecl *NewDecl);
380
381    ClassTemplatePartialSpecializationDecl *
382    InstantiateClassTemplatePartialSpecialization(
383                                              ClassTemplateDecl *ClassTemplate,
384                           ClassTemplatePartialSpecializationDecl *PartialSpec);
385  };
386}
387
388#endif // LLVM_CLANG_SEMA_TEMPLATE_H
389