SemaTemplateDeduction.cpp revision a27fad59dc760252af025ef6a86d31bb7d11a44a 
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    case Type::FunctionProto: {
269      const FunctionProtoType *FunctionProtoArg =
270        dyn_cast<FunctionProtoType>(Arg);
271      if (!FunctionProtoArg)
272        return false;
273
274      const FunctionProtoType *FunctionProtoParam =
275        cast<FunctionProtoType>(Param);
276
277      // Check return types.
278      if (!DeduceTemplateArguments(Context,
279                                   FunctionProtoParam->getResultType(),
280                                   FunctionProtoArg->getResultType(),
281                                   Deduced))
282        return false;
283
284      if (FunctionProtoParam->getNumArgs() != FunctionProtoArg->getNumArgs())
285        return false;
286
287      for (unsigned I = 0, N = FunctionProtoParam->getNumArgs(); I != N; ++I) {
288        // Check argument types.
289        if (!DeduceTemplateArguments(Context,
290                                     FunctionProtoParam->getArgType(I),
291                                     FunctionProtoArg->getArgType(I),
292                                     Deduced))
293          return false;
294      }
295
296      return true;
297    }
298
299    default:
300      break;
301  }
302
303  // FIXME: Many more cases to go (to go).
304  return false;
305}
306
307static bool
308DeduceTemplateArguments(ASTContext &Context, const TemplateArgument &Param,
309                        const TemplateArgument &Arg,
310                        llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
311  switch (Param.getKind()) {
312  case TemplateArgument::Null:
313    assert(false && "Null template argument in parameter list");
314    break;
315
316  case TemplateArgument::Type:
317    assert(Arg.getKind() == TemplateArgument::Type && "Type/value mismatch");
318    return DeduceTemplateArguments(Context, Param.getAsType(),
319                                   Arg.getAsType(), Deduced);
320
321  case TemplateArgument::Declaration:
322    // FIXME: Implement this check
323    assert(false && "Unimplemented template argument deduction case");
324    return false;
325
326  case TemplateArgument::Integral:
327    if (Arg.getKind() == TemplateArgument::Integral) {
328      // FIXME: Zero extension + sign checking here?
329      return *Param.getAsIntegral() == *Arg.getAsIntegral();
330    }
331    if (Arg.getKind() == TemplateArgument::Expression)
332      return false;
333
334    assert(false && "Type/value mismatch");
335    return false;
336
337  case TemplateArgument::Expression: {
338    if (NonTypeTemplateParmDecl *NTTP
339          = getDeducedParameterFromExpr(Param.getAsExpr())) {
340      if (Arg.getKind() == TemplateArgument::Integral)
341        // FIXME: Sign problems here
342        return DeduceNonTypeTemplateArgument(Context, NTTP,
343                                             *Arg.getAsIntegral(), Deduced);
344      if (Arg.getKind() == TemplateArgument::Expression)
345        return DeduceNonTypeTemplateArgument(Context, NTTP, Arg.getAsExpr(),
346                                             Deduced);
347
348      assert(false && "Type/value mismatch");
349      return false;
350    }
351
352    // Can't deduce anything, but that's okay.
353    return true;
354  }
355  }
356
357  return true;
358}
359
360static bool
361DeduceTemplateArguments(ASTContext &Context,
362                        const TemplateArgumentList &ParamList,
363                        const TemplateArgumentList &ArgList,
364                        llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
365  assert(ParamList.size() == ArgList.size());
366  for (unsigned I = 0, N = ParamList.size(); I != N; ++I) {
367    if (!DeduceTemplateArguments(Context, ParamList[I], ArgList[I], Deduced))
368      return false;
369  }
370  return true;
371}
372
373
374TemplateArgumentList *
375Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
376                              const TemplateArgumentList &TemplateArgs) {
377  // Deduce the template arguments for the partial specialization
378  llvm::SmallVector<TemplateArgument, 4> Deduced;
379  Deduced.resize(Partial->getTemplateParameters()->size());
380  if (! ::DeduceTemplateArguments(Context, Partial->getTemplateArgs(),
381                                  TemplateArgs, Deduced))
382    return 0;
383
384  // FIXME: Substitute the deduced template arguments into the template
385  // arguments of the class template partial specialization; the resulting
386  // template arguments should match TemplateArgs exactly.
387
388  for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
389    TemplateArgument &Arg = Deduced[I];
390
391    // FIXME: If this template argument was not deduced, but the corresponding
392    // template parameter has a default argument, instantiate the default
393    // argument.
394    if (Arg.isNull()) // FIXME: Result->Destroy(Context);
395      return 0;
396
397    if (Arg.getKind() == TemplateArgument::Integral) {
398      // FIXME: Instantiate the type, but we need some context!
399      const NonTypeTemplateParmDecl *Parm
400        = cast<NonTypeTemplateParmDecl>(Partial->getTemplateParameters()
401                                          ->getParam(I));
402      //      QualType T = InstantiateType(Parm->getType(), *Result,
403      //                                   Parm->getLocation(), Parm->getDeclName());
404      //      if (T.isNull()) // FIXME: Result->Destroy(Context);
405      //        return 0;
406      QualType T = Parm->getType();
407
408      // FIXME: Make sure we didn't overflow our data type!
409      llvm::APSInt &Value = *Arg.getAsIntegral();
410      unsigned AllowedBits = Context.getTypeSize(T);
411      if (Value.getBitWidth() != AllowedBits)
412        Value.extOrTrunc(AllowedBits);
413      Value.setIsSigned(T->isSignedIntegerType());
414      Arg.setIntegralType(T);
415    }
416  }
417
418  // FIXME: This is terrible. DeduceTemplateArguments should use a
419  // TemplateArgumentListBuilder directly.
420  TemplateArgumentListBuilder Builder(Context);
421  for (unsigned I = 0, N = Deduced.size(); I != N; ++I)
422    Builder.push_back(Deduced[I]);
423
424  return new (Context) TemplateArgumentList(Context, Builder, /*CopyArgs=*/true,
425                                            /*FlattenArgs=*/true);
426}
427