SemaTemplateDeduction.cpp revision 0233eb600f22b2023000778205f3ae1dfa3f5292 
1//===------- SemaTemplateDeduction.cpp - Template Argument Deduction ------===/
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 implements C++ template argument deduction.
10//
11//===----------------------------------------------------------------------===/
12
13#include "Sema.h"
14#include "clang/AST/ASTContext.h"
15#include "clang/AST/DeclTemplate.h"
16#include "clang/AST/StmtVisitor.h"
17#include "clang/AST/Expr.h"
18#include "clang/AST/ExprCXX.h"
19#include "clang/Parse/DeclSpec.h"
20#include "llvm/Support/Compiler.h"
21using namespace clang;
22
23/// \brief If the given expression is of a form that permits the deduction
24/// of a non-type template parameter, return the declaration of that
25/// non-type template parameter.
26static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
27  if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
28    E = IC->getSubExpr();
29
30  if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
31    return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
32
33  return 0;
34}
35
36/// \brief Deduce the value of the given non-type template parameter
37/// from the given constant.
38///
39/// \returns true if deduction succeeded, false otherwise.
40static bool DeduceNonTypeTemplateArgument(ASTContext &Context,
41                                          NonTypeTemplateParmDecl *NTTP,
42                                          llvm::APInt Value,
43                             llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
44  assert(NTTP->getDepth() == 0 &&
45         "Cannot deduce non-type template argument with depth > 0");
46
47  if (Deduced[NTTP->getIndex()].isNull()) {
48    Deduced[NTTP->getIndex()] = TemplateArgument(SourceLocation(),
49                                                 llvm::APSInt(Value),
50                                                 NTTP->getType());
51    return true;
52  }
53
54  if (Deduced[NTTP->getIndex()].getKind() != TemplateArgument::Integral)
55    return false;
56
57  // If the template argument was previously deduced to a negative value,
58  // then our deduction fails.
59  const llvm::APSInt *PrevValuePtr = Deduced[NTTP->getIndex()].getAsIntegral();
60  assert(PrevValuePtr && "Not an integral template argument?");
61  if (PrevValuePtr->isSigned() && PrevValuePtr->isNegative())
62    return false;
63
64  llvm::APInt PrevValue = *PrevValuePtr;
65  if (Value.getBitWidth() > PrevValue.getBitWidth())
66    PrevValue.zext(Value.getBitWidth());
67  else if (Value.getBitWidth() < PrevValue.getBitWidth())
68    Value.zext(PrevValue.getBitWidth());
69  return Value == PrevValue;
70}
71
72/// \brief Deduce the value of the given non-type template parameter
73/// from the given type- or value-dependent expression.
74///
75/// \returns true if deduction succeeded, false otherwise.
76
77static bool DeduceNonTypeTemplateArgument(ASTContext &Context,
78                                          NonTypeTemplateParmDecl *NTTP,
79                                          Expr *Value,
80                            llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
81  assert(NTTP->getDepth() == 0 &&
82         "Cannot deduce non-type template argument with depth > 0");
83  assert((Value->isTypeDependent() || Value->isValueDependent()) &&
84         "Expression template argument must be type- or value-dependent.");
85
86  if (Deduced[NTTP->getIndex()].isNull()) {
87    // FIXME: Clone the Value?
88    Deduced[NTTP->getIndex()] = TemplateArgument(Value);
89    return true;
90  }
91
92  if (Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Integral) {
93    // Okay, we deduced a constant in one case and a dependent expression
94    // in another case. FIXME: Later, we will check that instantiating the
95    // dependent expression gives us the constant value.
96    return true;
97  }
98
99  // FIXME: Compare the expressions for equality!
100  return true;
101}
102
103static bool DeduceTemplateArguments(ASTContext &Context, QualType Param,
104                                    QualType Arg,
105                             llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
106  // We only want to look at the canonical types, since typedefs and
107  // sugar are not part of template argument deduction.
108  Param = Context.getCanonicalType(Param);
109  Arg = Context.getCanonicalType(Arg);
110
111  // If the parameter type is not dependent, just compare the types
112  // directly.
113  if (!Param->isDependentType())
114    return Param == Arg;
115
116  // C++ [temp.deduct.type]p9:
117  //
118  //   A template type argument T, a template template argument TT or a
119  //   template non-type argument i can be deduced if P and A have one of
120  //   the following forms:
121  //
122  //     T
123  //     cv-list T
124  if (const TemplateTypeParmType *TemplateTypeParm
125        = Param->getAsTemplateTypeParmType()) {
126    // The argument type can not be less qualified than the parameter
127    // type.
128    if (Param.isMoreQualifiedThan(Arg))
129      return false;
130
131    assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0");
132
133    unsigned Quals = Arg.getCVRQualifiers() & ~Param.getCVRQualifiers();
134    QualType DeducedType = Arg.getQualifiedType(Quals);
135	  unsigned Index = TemplateTypeParm->getIndex();
136
137    if (Deduced[Index].isNull())
138      Deduced[Index] = TemplateArgument(SourceLocation(), DeducedType);
139    else {
140      // C++ [temp.deduct.type]p2:
141      //   [...] If type deduction cannot be done for any P/A pair, or if for
142      //   any pair the deduction leads to more than one possible set of
143      //   deduced values, or if different pairs yield different deduced
144      //   values, or if any template argument remains neither deduced nor
145      //   explicitly specified, template argument deduction fails.
146      if (Deduced[Index].getAsType() != DeducedType)
147        return false;
148    }
149    return true;
150  }
151
152  if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
153    return false;
154
155  switch (Param->getTypeClass()) {
156    // No deduction possible for these types
157    case Type::Builtin:
158      return false;
159
160
161    //     T *
162    case Type::Pointer: {
163      const PointerType *PointerArg = Arg->getAsPointerType();
164      if (!PointerArg)
165        return false;
166
167      return DeduceTemplateArguments(Context,
168                                   cast<PointerType>(Param)->getPointeeType(),
169                                     PointerArg->getPointeeType(),
170                                     Deduced);
171    }
172
173    //     T &
174    case Type::LValueReference: {
175      const LValueReferenceType *ReferenceArg = Arg->getAsLValueReferenceType();
176      if (!ReferenceArg)
177        return false;
178
179      return DeduceTemplateArguments(Context,
180                           cast<LValueReferenceType>(Param)->getPointeeType(),
181                                     ReferenceArg->getPointeeType(),
182                                     Deduced);
183    }
184
185    //     T && [C++0x]
186    case Type::RValueReference: {
187      const RValueReferenceType *ReferenceArg = Arg->getAsRValueReferenceType();
188      if (!ReferenceArg)
189        return false;
190
191      return DeduceTemplateArguments(Context,
192                           cast<RValueReferenceType>(Param)->getPointeeType(),
193                                     ReferenceArg->getPointeeType(),
194                                     Deduced);
195    }
196
197    //     T [] (implied, but not stated explicitly)
198    case Type::IncompleteArray: {
199      const IncompleteArrayType *IncompleteArrayArg =
200        Context.getAsIncompleteArrayType(Arg);
201      if (!IncompleteArrayArg)
202        return false;
203
204      return DeduceTemplateArguments(Context,
205                     Context.getAsIncompleteArrayType(Param)->getElementType(),
206                                     IncompleteArrayArg->getElementType(),
207                                     Deduced);
208    }
209
210    //     T [integer-constant]
211    case Type::ConstantArray: {
212      const ConstantArrayType *ConstantArrayArg =
213        Context.getAsConstantArrayType(Arg);
214      if (!ConstantArrayArg)
215        return false;
216
217      const ConstantArrayType *ConstantArrayParm =
218        Context.getAsConstantArrayType(Param);
219      if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
220        return false;
221
222      return DeduceTemplateArguments(Context,
223                                     ConstantArrayParm->getElementType(),
224                                     ConstantArrayArg->getElementType(),
225                                     Deduced);
226    }
227
228    //     type [i]
229    case Type::DependentSizedArray: {
230      const ArrayType *ArrayArg = dyn_cast<ArrayType>(Arg);
231      if (!ArrayArg)
232        return false;
233
234      // Check the element type of the arrays
235      const DependentSizedArrayType *DependentArrayParm
236        = cast<DependentSizedArrayType>(Param);
237      if (!DeduceTemplateArguments(Context,
238                                   DependentArrayParm->getElementType(),
239                                   ArrayArg->getElementType(),
240                                   Deduced))
241        return false;
242
243      // Determine the array bound is something we can deduce.
244      NonTypeTemplateParmDecl *NTTP
245        = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr());
246      if (!NTTP)
247        return true;
248
249      // We can perform template argument deduction for the given non-type
250      // template parameter.
251      assert(NTTP->getDepth() == 0 &&
252             "Cannot deduce non-type template argument at depth > 0");
253      if (const ConstantArrayType *ConstantArrayArg
254            = dyn_cast<ConstantArrayType>(ArrayArg))
255        return DeduceNonTypeTemplateArgument(Context, NTTP,
256                                             ConstantArrayArg->getSize(),
257                                             Deduced);
258      if (const DependentSizedArrayType *DependentArrayArg
259            = dyn_cast<DependentSizedArrayType>(ArrayArg))
260        return DeduceNonTypeTemplateArgument(Context, NTTP,
261                                             DependentArrayArg->getSizeExpr(),
262                                             Deduced);
263
264      // Incomplete type does not match a dependently-sized array type
265      return false;
266    }
267
268    default:
269      break;
270  }
271
272  // FIXME: Many more cases to go (to go).
273  return false;
274}
275
276static bool
277DeduceTemplateArguments(ASTContext &Context, const TemplateArgument &Param,
278                        const TemplateArgument &Arg,
279                        llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
280  switch (Param.getKind()) {
281  case TemplateArgument::Null:
282    assert(false && "Null template argument in parameter list");
283    break;
284
285  case TemplateArgument::Type:
286    assert(Arg.getKind() == TemplateArgument::Type && "Type/value mismatch");
287    return DeduceTemplateArguments(Context, Param.getAsType(),
288                                   Arg.getAsType(), Deduced);
289
290  case TemplateArgument::Declaration:
291    // FIXME: Implement this check
292    assert(false && "Unimplemented template argument deduction case");
293    return false;
294
295  case TemplateArgument::Integral:
296    if (Arg.getKind() == TemplateArgument::Integral) {
297      // FIXME: Zero extension + sign checking here?
298      return *Param.getAsIntegral() == *Arg.getAsIntegral();
299    }
300    if (Arg.getKind() == TemplateArgument::Expression)
301      return false;
302
303    assert(false && "Type/value mismatch");
304    return false;
305
306  case TemplateArgument::Expression: {
307    if (NonTypeTemplateParmDecl *NTTP
308          = getDeducedParameterFromExpr(Param.getAsExpr())) {
309      if (Arg.getKind() == TemplateArgument::Integral)
310        // FIXME: Sign problems here
311        return DeduceNonTypeTemplateArgument(Context, NTTP,
312                                             *Arg.getAsIntegral(), Deduced);
313      if (Arg.getKind() == TemplateArgument::Expression)
314        return DeduceNonTypeTemplateArgument(Context, NTTP, Arg.getAsExpr(),
315                                             Deduced);
316
317      assert(false && "Type/value mismatch");
318      return false;
319    }
320
321    // Can't deduce anything, but that's okay.
322    return true;
323  }
324  }
325
326  return true;
327}
328
329static bool
330DeduceTemplateArguments(ASTContext &Context,
331                        const TemplateArgumentList &ParamList,
332                        const TemplateArgumentList &ArgList,
333                        llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
334  assert(ParamList.size() == ArgList.size());
335  for (unsigned I = 0, N = ParamList.size(); I != N; ++I) {
336    if (!DeduceTemplateArguments(Context, ParamList[I], ArgList[I], Deduced))
337      return false;
338  }
339  return true;
340}
341
342
343TemplateArgumentList *
344Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
345                              const TemplateArgumentList &TemplateArgs) {
346  // Deduce the template arguments for the partial specialization
347  llvm::SmallVector<TemplateArgument, 4> Deduced;
348  Deduced.resize(Partial->getTemplateParameters()->size());
349  if (! ::DeduceTemplateArguments(Context, Partial->getTemplateArgs(),
350                                  TemplateArgs, Deduced))
351    return 0;
352
353  // FIXME: Substitute the deduced template arguments into the template
354  // arguments of the class template partial specialization; the resulting
355  // template arguments should match TemplateArgs exactly.
356
357  for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
358    TemplateArgument &Arg = Deduced[I];
359
360    // FIXME: If this template argument was not deduced, but the corresponding
361    // template parameter has a default argument, instantiate the default
362    // argument.
363    if (Arg.isNull()) // FIXME: Result->Destroy(Context);
364      return 0;
365
366    if (Arg.getKind() == TemplateArgument::Integral) {
367      // FIXME: Instantiate the type, but we need some context!
368      const NonTypeTemplateParmDecl *Parm
369        = cast<NonTypeTemplateParmDecl>(Partial->getTemplateParameters()
370                                          ->getParam(I));
371      //      QualType T = InstantiateType(Parm->getType(), *Result,
372      //                                   Parm->getLocation(), Parm->getDeclName());
373      //      if (T.isNull()) // FIXME: Result->Destroy(Context);
374      //        return 0;
375      QualType T = Parm->getType();
376
377      // FIXME: Make sure we didn't overflow our data type!
378      llvm::APSInt &Value = *Arg.getAsIntegral();
379      unsigned AllowedBits = Context.getTypeSize(T);
380      if (Value.getBitWidth() != AllowedBits)
381        Value.extOrTrunc(AllowedBits);
382      Value.setIsSigned(T->isSignedIntegerType());
383      Arg.setIntegralType(T);
384    }
385  }
386
387  // FIXME: This is terrible. DeduceTemplateArguments should use a
388  // TemplateArgumentListBuilder directly.
389  TemplateArgumentListBuilder Builder;
390  for (unsigned I = 0, N = Deduced.size(); I != N; ++I)
391    Builder.push_back(Deduced[I]);
392
393  return new (Context) TemplateArgumentList(Context, Builder, /*CopyArgs=*/true,
394                                            /*FlattenArgs=*/true);
395}
396