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    /// \brief The template argument list at a certain template depth
44    typedef ArrayRef<TemplateArgument> ArgList;
45
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    /// \brief The number of outer levels of template arguments that are not
51    /// being substituted.
52    unsigned NumRetainedOuterLevels = 0;
53
54  public:
55    /// \brief Construct an empty set of template argument lists.
56    MultiLevelTemplateArgumentList() { }
57
58    /// \brief Construct a single-level template argument list.
59    explicit
60    MultiLevelTemplateArgumentList(const TemplateArgumentList &TemplateArgs) {
61      addOuterTemplateArguments(&TemplateArgs);
62    }
63
64    /// \brief Determine the number of levels in this template argument
65    /// list.
66    unsigned getNumLevels() const {
67      return TemplateArgumentLists.size() + NumRetainedOuterLevels;
68    }
69
70    /// \brief Determine the number of substituted levels in this template
71    /// argument list.
72    unsigned getNumSubstitutedLevels() const {
73      return TemplateArgumentLists.size();
74    }
75
76    /// \brief Retrieve the template argument at a given depth and index.
77    const TemplateArgument &operator()(unsigned Depth, unsigned Index) const {
78      assert(NumRetainedOuterLevels <= Depth && Depth < getNumLevels());
79      assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size());
80      return TemplateArgumentLists[getNumLevels() - Depth - 1][Index];
81    }
82
83    /// \brief Determine whether there is a non-NULL template argument at the
84    /// given depth and index.
85    ///
86    /// There must exist a template argument list at the given depth.
87    bool hasTemplateArgument(unsigned Depth, unsigned Index) const {
88      assert(Depth < getNumLevels());
89
90      if (Depth < NumRetainedOuterLevels)
91        return false;
92
93      if (Index >= TemplateArgumentLists[getNumLevels() - Depth - 1].size())
94        return false;
95
96      return !(*this)(Depth, Index).isNull();
97    }
98
99    /// \brief Clear out a specific template argument.
100    void setArgument(unsigned Depth, unsigned Index,
101                     TemplateArgument Arg) {
102      assert(NumRetainedOuterLevels <= Depth && Depth < getNumLevels());
103      assert(Index < TemplateArgumentLists[getNumLevels() - Depth - 1].size());
104      const_cast<TemplateArgument&>(
105                TemplateArgumentLists[getNumLevels() - Depth - 1][Index])
106        = Arg;
107    }
108
109    /// \brief Add a new outermost level to the multi-level template argument
110    /// list.
111    void addOuterTemplateArguments(const TemplateArgumentList *TemplateArgs) {
112      addOuterTemplateArguments(ArgList(TemplateArgs->data(),
113                                        TemplateArgs->size()));
114    }
115
116    /// \brief Add a new outmost level to the multi-level template argument
117    /// list.
118    void addOuterTemplateArguments(ArgList Args) {
119      assert(!NumRetainedOuterLevels &&
120             "substituted args outside retained args?");
121      TemplateArgumentLists.push_back(Args);
122    }
123
124    /// \brief Add an outermost level that we are not substituting. We have no
125    /// arguments at this level, and do not remove it from the depth of inner
126    /// template parameters that we instantiate.
127    void addOuterRetainedLevel() {
128      ++NumRetainedOuterLevels;
129    }
130
131    /// \brief Retrieve the innermost template argument list.
132    const ArgList &getInnermost() const {
133      return TemplateArgumentLists.front();
134    }
135  };
136
137  /// \brief The context in which partial ordering of function templates occurs.
138  enum TPOC {
139    /// \brief Partial ordering of function templates for a function call.
140    TPOC_Call,
141    /// \brief Partial ordering of function templates for a call to a
142    /// conversion function.
143    TPOC_Conversion,
144    /// \brief Partial ordering of function templates in other contexts, e.g.,
145    /// taking the address of a function template or matching a function
146    /// template specialization to a function template.
147    TPOC_Other
148  };
149
150  // This is lame but unavoidable in a world without forward
151  // declarations of enums.  The alternatives are to either pollute
152  // Sema.h (by including this file) or sacrifice type safety (by
153  // making Sema.h declare things as enums).
154  class TemplatePartialOrderingContext {
155    TPOC Value;
156  public:
157    TemplatePartialOrderingContext(TPOC Value) : Value(Value) {}
158    operator TPOC() const { return Value; }
159  };
160
161  /// \brief Captures a template argument whose value has been deduced
162  /// via c++ template argument deduction.
163  class DeducedTemplateArgument : public TemplateArgument {
164    /// \brief For a non-type template argument, whether the value was
165    /// deduced from an array bound.
166    bool DeducedFromArrayBound;
167
168  public:
169    DeducedTemplateArgument()
170      : TemplateArgument(), DeducedFromArrayBound(false) { }
171
172    DeducedTemplateArgument(const TemplateArgument &Arg,
173                            bool DeducedFromArrayBound = false)
174      : TemplateArgument(Arg), DeducedFromArrayBound(DeducedFromArrayBound) { }
175
176    /// \brief Construct an integral non-type template argument that
177    /// has been deduced, possibly from an array bound.
178    DeducedTemplateArgument(ASTContext &Ctx,
179                            const llvm::APSInt &Value,
180                            QualType ValueType,
181                            bool DeducedFromArrayBound)
182      : TemplateArgument(Ctx, Value, ValueType),
183        DeducedFromArrayBound(DeducedFromArrayBound) { }
184
185    /// \brief For a non-type template argument, determine whether the
186    /// template argument was deduced from an array bound.
187    bool wasDeducedFromArrayBound() const { return DeducedFromArrayBound; }
188
189    /// \brief Specify whether the given non-type template argument
190    /// was deduced from an array bound.
191    void setDeducedFromArrayBound(bool Deduced) {
192      DeducedFromArrayBound = Deduced;
193    }
194  };
195
196  /// \brief A stack-allocated class that identifies which local
197  /// variable declaration instantiations are present in this scope.
198  ///
199  /// A new instance of this class type will be created whenever we
200  /// instantiate a new function declaration, which will have its own
201  /// set of parameter declarations.
202  class LocalInstantiationScope {
203  public:
204    /// \brief A set of declarations.
205    typedef SmallVector<ParmVarDecl *, 4> DeclArgumentPack;
206
207  private:
208    /// \brief Reference to the semantic analysis that is performing
209    /// this template instantiation.
210    Sema &SemaRef;
211
212    typedef llvm::SmallDenseMap<
213        const Decl *, llvm::PointerUnion<Decl *, DeclArgumentPack *>, 4>
214    LocalDeclsMap;
215
216    /// \brief A mapping from local declarations that occur
217    /// within a template to their instantiations.
218    ///
219    /// This mapping is used during instantiation to keep track of,
220    /// e.g., function parameter and variable declarations. For example,
221    /// given:
222    ///
223    /// \code
224    ///   template<typename T> T add(T x, T y) { return x + y; }
225    /// \endcode
226    ///
227    /// when we instantiate add<int>, we will introduce a mapping from
228    /// the ParmVarDecl for 'x' that occurs in the template to the
229    /// instantiated ParmVarDecl for 'x'.
230    ///
231    /// For a parameter pack, the local instantiation scope may contain a
232    /// set of instantiated parameters. This is stored as a DeclArgumentPack
233    /// pointer.
234    LocalDeclsMap LocalDecls;
235
236    /// \brief The set of argument packs we've allocated.
237    SmallVector<DeclArgumentPack *, 1> ArgumentPacks;
238
239    /// \brief The outer scope, which contains local variable
240    /// definitions from some other instantiation (that may not be
241    /// relevant to this particular scope).
242    LocalInstantiationScope *Outer;
243
244    /// \brief Whether we have already exited this scope.
245    bool Exited;
246
247    /// \brief Whether to combine this scope with the outer scope, such that
248    /// lookup will search our outer scope.
249    bool CombineWithOuterScope;
250
251    /// \brief If non-NULL, the template parameter pack that has been
252    /// partially substituted per C++0x [temp.arg.explicit]p9.
253    NamedDecl *PartiallySubstitutedPack;
254
255    /// \brief If \c PartiallySubstitutedPack is non-null, the set of
256    /// explicitly-specified template arguments in that pack.
257    const TemplateArgument *ArgsInPartiallySubstitutedPack;
258
259    /// \brief If \c PartiallySubstitutedPack, the number of
260    /// explicitly-specified template arguments in
261    /// ArgsInPartiallySubstitutedPack.
262    unsigned NumArgsInPartiallySubstitutedPack;
263
264    // This class is non-copyable
265    LocalInstantiationScope(
266      const LocalInstantiationScope &) = delete;
267    void operator=(const LocalInstantiationScope &) = delete;
268
269  public:
270    LocalInstantiationScope(Sema &SemaRef, bool CombineWithOuterScope = false)
271      : SemaRef(SemaRef), Outer(SemaRef.CurrentInstantiationScope),
272        Exited(false), CombineWithOuterScope(CombineWithOuterScope),
273        PartiallySubstitutedPack(nullptr)
274    {
275      SemaRef.CurrentInstantiationScope = this;
276    }
277
278    ~LocalInstantiationScope() {
279      Exit();
280    }
281
282    const Sema &getSema() const { return SemaRef; }
283
284    /// \brief Exit this local instantiation scope early.
285    void Exit() {
286      if (Exited)
287        return;
288
289      for (unsigned I = 0, N = ArgumentPacks.size(); I != N; ++I)
290        delete ArgumentPacks[I];
291
292      SemaRef.CurrentInstantiationScope = Outer;
293      Exited = true;
294    }
295
296    /// \brief Clone this scope, and all outer scopes, down to the given
297    /// outermost scope.
298    LocalInstantiationScope *cloneScopes(LocalInstantiationScope *Outermost) {
299      if (this == Outermost) return this;
300
301      // Save the current scope from SemaRef since the LocalInstantiationScope
302      // will overwrite it on construction
303      LocalInstantiationScope *oldScope = SemaRef.CurrentInstantiationScope;
304
305      LocalInstantiationScope *newScope =
306        new LocalInstantiationScope(SemaRef, CombineWithOuterScope);
307
308      newScope->Outer = nullptr;
309      if (Outer)
310        newScope->Outer = Outer->cloneScopes(Outermost);
311
312      newScope->PartiallySubstitutedPack = PartiallySubstitutedPack;
313      newScope->ArgsInPartiallySubstitutedPack = ArgsInPartiallySubstitutedPack;
314      newScope->NumArgsInPartiallySubstitutedPack =
315        NumArgsInPartiallySubstitutedPack;
316
317      for (LocalDeclsMap::iterator I = LocalDecls.begin(), E = LocalDecls.end();
318           I != E; ++I) {
319        const Decl *D = I->first;
320        llvm::PointerUnion<Decl *, DeclArgumentPack *> &Stored =
321          newScope->LocalDecls[D];
322        if (I->second.is<Decl *>()) {
323          Stored = I->second.get<Decl *>();
324        } else {
325          DeclArgumentPack *OldPack = I->second.get<DeclArgumentPack *>();
326          DeclArgumentPack *NewPack = new DeclArgumentPack(*OldPack);
327          Stored = NewPack;
328          newScope->ArgumentPacks.push_back(NewPack);
329        }
330      }
331      // Restore the saved scope to SemaRef
332      SemaRef.CurrentInstantiationScope = oldScope;
333      return newScope;
334    }
335
336    /// \brief deletes the given scope, and all otuer scopes, down to the
337    /// given outermost scope.
338    static void deleteScopes(LocalInstantiationScope *Scope,
339                             LocalInstantiationScope *Outermost) {
340      while (Scope && Scope != Outermost) {
341        LocalInstantiationScope *Out = Scope->Outer;
342        delete Scope;
343        Scope = Out;
344      }
345    }
346
347    /// \brief Find the instantiation of the declaration D within the current
348    /// instantiation scope.
349    ///
350    /// \param D The declaration whose instantiation we are searching for.
351    ///
352    /// \returns A pointer to the declaration or argument pack of declarations
353    /// to which the declaration \c D is instantiated, if found. Otherwise,
354    /// returns NULL.
355    llvm::PointerUnion<Decl *, DeclArgumentPack *> *
356    findInstantiationOf(const Decl *D);
357
358    void InstantiatedLocal(const Decl *D, Decl *Inst);
359    void InstantiatedLocalPackArg(const Decl *D, ParmVarDecl *Inst);
360    void MakeInstantiatedLocalArgPack(const Decl *D);
361
362    /// \brief Note that the given parameter pack has been partially substituted
363    /// via explicit specification of template arguments
364    /// (C++0x [temp.arg.explicit]p9).
365    ///
366    /// \param Pack The parameter pack, which will always be a template
367    /// parameter pack.
368    ///
369    /// \param ExplicitArgs The explicitly-specified template arguments provided
370    /// for this parameter pack.
371    ///
372    /// \param NumExplicitArgs The number of explicitly-specified template
373    /// arguments provided for this parameter pack.
374    void SetPartiallySubstitutedPack(NamedDecl *Pack,
375                                     const TemplateArgument *ExplicitArgs,
376                                     unsigned NumExplicitArgs);
377
378    /// \brief Reset the partially-substituted pack when it is no longer of
379    /// interest.
380    void ResetPartiallySubstitutedPack() {
381      assert(PartiallySubstitutedPack && "No partially-substituted pack");
382      PartiallySubstitutedPack = nullptr;
383      ArgsInPartiallySubstitutedPack = nullptr;
384      NumArgsInPartiallySubstitutedPack = 0;
385    }
386
387    /// \brief Retrieve the partially-substitued template parameter pack.
388    ///
389    /// If there is no partially-substituted parameter pack, returns NULL.
390    NamedDecl *
391    getPartiallySubstitutedPack(const TemplateArgument **ExplicitArgs = nullptr,
392                                unsigned *NumExplicitArgs = nullptr) const;
393  };
394
395  class TemplateDeclInstantiator
396    : public DeclVisitor<TemplateDeclInstantiator, Decl *>
397  {
398    Sema &SemaRef;
399    Sema::ArgumentPackSubstitutionIndexRAII SubstIndex;
400    DeclContext *Owner;
401    const MultiLevelTemplateArgumentList &TemplateArgs;
402    Sema::LateInstantiatedAttrVec* LateAttrs;
403    LocalInstantiationScope *StartingScope;
404
405    /// \brief A list of out-of-line class template partial
406    /// specializations that will need to be instantiated after the
407    /// enclosing class's instantiation is complete.
408    SmallVector<std::pair<ClassTemplateDecl *,
409                                ClassTemplatePartialSpecializationDecl *>, 4>
410      OutOfLinePartialSpecs;
411
412    /// \brief A list of out-of-line variable template partial
413    /// specializations that will need to be instantiated after the
414    /// enclosing variable's instantiation is complete.
415    /// FIXME: Verify that this is needed.
416    SmallVector<
417        std::pair<VarTemplateDecl *, VarTemplatePartialSpecializationDecl *>, 4>
418    OutOfLineVarPartialSpecs;
419
420  public:
421    TemplateDeclInstantiator(Sema &SemaRef, DeclContext *Owner,
422                             const MultiLevelTemplateArgumentList &TemplateArgs)
423      : SemaRef(SemaRef),
424        SubstIndex(SemaRef, SemaRef.ArgumentPackSubstitutionIndex),
425        Owner(Owner), TemplateArgs(TemplateArgs), LateAttrs(nullptr),
426        StartingScope(nullptr) {}
427
428// Define all the decl visitors using DeclNodes.inc
429#define DECL(DERIVED, BASE) \
430    Decl *Visit ## DERIVED ## Decl(DERIVED ## Decl *D);
431#define ABSTRACT_DECL(DECL)
432
433// Decls which never appear inside a class or function.
434#define OBJCCONTAINER(DERIVED, BASE)
435#define FILESCOPEASM(DERIVED, BASE)
436#define IMPORT(DERIVED, BASE)
437#define EXPORT(DERIVED, BASE)
438#define LINKAGESPEC(DERIVED, BASE)
439#define OBJCCOMPATIBLEALIAS(DERIVED, BASE)
440#define OBJCMETHOD(DERIVED, BASE)
441#define OBJCTYPEPARAM(DERIVED, BASE)
442#define OBJCIVAR(DERIVED, BASE)
443#define OBJCPROPERTY(DERIVED, BASE)
444#define OBJCPROPERTYIMPL(DERIVED, BASE)
445#define EMPTY(DERIVED, BASE)
446
447// Decls which use special-case instantiation code.
448#define BLOCK(DERIVED, BASE)
449#define CAPTURED(DERIVED, BASE)
450#define IMPLICITPARAM(DERIVED, BASE)
451
452#include "clang/AST/DeclNodes.inc"
453
454    // A few supplemental visitor functions.
455    Decl *VisitCXXMethodDecl(CXXMethodDecl *D,
456                             TemplateParameterList *TemplateParams,
457                             bool IsClassScopeSpecialization = false);
458    Decl *VisitFunctionDecl(FunctionDecl *D,
459                            TemplateParameterList *TemplateParams);
460    Decl *VisitDecl(Decl *D);
461    Decl *VisitVarDecl(VarDecl *D, bool InstantiatingVarTemplate,
462                       ArrayRef<BindingDecl *> *Bindings = nullptr);
463
464    // Enable late instantiation of attributes.  Late instantiated attributes
465    // will be stored in LA.
466    void enableLateAttributeInstantiation(Sema::LateInstantiatedAttrVec *LA) {
467      LateAttrs = LA;
468      StartingScope = SemaRef.CurrentInstantiationScope;
469    }
470
471    // Disable late instantiation of attributes.
472    void disableLateAttributeInstantiation() {
473      LateAttrs = nullptr;
474      StartingScope = nullptr;
475    }
476
477    LocalInstantiationScope *getStartingScope() const { return StartingScope; }
478
479    typedef
480      SmallVectorImpl<std::pair<ClassTemplateDecl *,
481                                     ClassTemplatePartialSpecializationDecl *> >
482        ::iterator
483      delayed_partial_spec_iterator;
484
485    typedef SmallVectorImpl<std::pair<
486        VarTemplateDecl *, VarTemplatePartialSpecializationDecl *> >::iterator
487    delayed_var_partial_spec_iterator;
488
489    /// \brief Return an iterator to the beginning of the set of
490    /// "delayed" partial specializations, which must be passed to
491    /// InstantiateClassTemplatePartialSpecialization once the class
492    /// definition has been completed.
493    delayed_partial_spec_iterator delayed_partial_spec_begin() {
494      return OutOfLinePartialSpecs.begin();
495    }
496
497    delayed_var_partial_spec_iterator delayed_var_partial_spec_begin() {
498      return OutOfLineVarPartialSpecs.begin();
499    }
500
501    /// \brief Return an iterator to the end of the set of
502    /// "delayed" partial specializations, which must be passed to
503    /// InstantiateClassTemplatePartialSpecialization once the class
504    /// definition has been completed.
505    delayed_partial_spec_iterator delayed_partial_spec_end() {
506      return OutOfLinePartialSpecs.end();
507    }
508
509    delayed_var_partial_spec_iterator delayed_var_partial_spec_end() {
510      return OutOfLineVarPartialSpecs.end();
511    }
512
513    // Helper functions for instantiating methods.
514    TypeSourceInfo *SubstFunctionType(FunctionDecl *D,
515                             SmallVectorImpl<ParmVarDecl *> &Params);
516    bool InitFunctionInstantiation(FunctionDecl *New, FunctionDecl *Tmpl);
517    bool InitMethodInstantiation(CXXMethodDecl *New, CXXMethodDecl *Tmpl);
518
519    TemplateParameterList *
520      SubstTemplateParams(TemplateParameterList *List);
521
522    bool SubstQualifier(const DeclaratorDecl *OldDecl,
523                        DeclaratorDecl *NewDecl);
524    bool SubstQualifier(const TagDecl *OldDecl,
525                        TagDecl *NewDecl);
526
527    Decl *VisitVarTemplateSpecializationDecl(
528        VarTemplateDecl *VarTemplate, VarDecl *FromVar, void *InsertPos,
529        const TemplateArgumentListInfo &TemplateArgsInfo,
530        ArrayRef<TemplateArgument> Converted);
531
532    Decl *InstantiateTypedefNameDecl(TypedefNameDecl *D, bool IsTypeAlias);
533    ClassTemplatePartialSpecializationDecl *
534    InstantiateClassTemplatePartialSpecialization(
535                                              ClassTemplateDecl *ClassTemplate,
536                           ClassTemplatePartialSpecializationDecl *PartialSpec);
537    VarTemplatePartialSpecializationDecl *
538    InstantiateVarTemplatePartialSpecialization(
539        VarTemplateDecl *VarTemplate,
540        VarTemplatePartialSpecializationDecl *PartialSpec);
541    void InstantiateEnumDefinition(EnumDecl *Enum, EnumDecl *Pattern);
542
543  private:
544    template<typename T>
545    Decl *instantiateUnresolvedUsingDecl(T *D,
546                                         bool InstantiatingPackElement = false);
547  };
548}
549
550#endif // LLVM_CLANG_SEMA_TEMPLATE_H
551