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"
21 using namespace clang;
22 
23 static bool
24 DeduceTemplateArguments(ASTContext &Context, const TemplateArgument &Param,
25                         const TemplateArgument &Arg,
26                         llvm::SmallVectorImpl<TemplateArgument> &Deduced);
27 
28 /// \brief If the given expression is of a form that permits the deduction
29 /// of a non-type template parameter, return the declaration of that
30 /// non-type template parameter.
31 static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
32   if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E))
33     E = IC->getSubExpr();
34 
35   if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E))
36     return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl());
37 
38   return 0;
39 }
40 
41 /// \brief Deduce the value of the given non-type template parameter
42 /// from the given constant.
43 ///
44 /// \returns true if deduction succeeded, false otherwise.
45 static bool DeduceNonTypeTemplateArgument(ASTContext &Context,
46                                           NonTypeTemplateParmDecl *NTTP,
47                                           llvm::APInt Value,
48                              llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
49   assert(NTTP->getDepth() == 0 &&
50          "Cannot deduce non-type template argument with depth > 0");
51 
52   if (Deduced[NTTP->getIndex()].isNull()) {
53     Deduced[NTTP->getIndex()] = TemplateArgument(SourceLocation(),
54                                                  llvm::APSInt(Value),
55                                                  NTTP->getType());
56     return true;
57   }
58 
59   if (Deduced[NTTP->getIndex()].getKind() != TemplateArgument::Integral)
60     return false;
61 
62   // If the template argument was previously deduced to a negative value,
63   // then our deduction fails.
64   const llvm::APSInt *PrevValuePtr = Deduced[NTTP->getIndex()].getAsIntegral();
65   assert(PrevValuePtr && "Not an integral template argument?");
66   if (PrevValuePtr->isSigned() && PrevValuePtr->isNegative())
67     return false;
68 
69   llvm::APInt PrevValue = *PrevValuePtr;
70   if (Value.getBitWidth() > PrevValue.getBitWidth())
71     PrevValue.zext(Value.getBitWidth());
72   else if (Value.getBitWidth() < PrevValue.getBitWidth())
73     Value.zext(PrevValue.getBitWidth());
74   return Value == PrevValue;
75 }
76 
77 /// \brief Deduce the value of the given non-type template parameter
78 /// from the given type- or value-dependent expression.
79 ///
80 /// \returns true if deduction succeeded, false otherwise.
81 
82 static bool DeduceNonTypeTemplateArgument(ASTContext &Context,
83                                           NonTypeTemplateParmDecl *NTTP,
84                                           Expr *Value,
85                             llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
86   assert(NTTP->getDepth() == 0 &&
87          "Cannot deduce non-type template argument with depth > 0");
88   assert((Value->isTypeDependent() || Value->isValueDependent()) &&
89          "Expression template argument must be type- or value-dependent.");
90 
91   if (Deduced[NTTP->getIndex()].isNull()) {
92     // FIXME: Clone the Value?
93     Deduced[NTTP->getIndex()] = TemplateArgument(Value);
94     return true;
95   }
96 
97   if (Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Integral) {
98     // Okay, we deduced a constant in one case and a dependent expression
99     // in another case. FIXME: Later, we will check that instantiating the
100     // dependent expression gives us the constant value.
101     return true;
102   }
103 
104   // FIXME: Compare the expressions for equality!
105   return true;
106 }
107 
108 static bool DeduceTemplateArguments(ASTContext &Context,
109                                     TemplateName Param,
110                                     TemplateName Arg,
111                              llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
112   // FIXME: Implement template argument deduction for template
113   // template parameters.
114 
115   TemplateDecl *ParamDecl = Param.getAsTemplateDecl();
116   TemplateDecl *ArgDecl = Arg.getAsTemplateDecl();
117 
118   if (!ParamDecl || !ArgDecl)
119     return false;
120 
121   ParamDecl = cast<TemplateDecl>(Context.getCanonicalDecl(ParamDecl));
122   ArgDecl = cast<TemplateDecl>(Context.getCanonicalDecl(ArgDecl));
123   return ParamDecl == ArgDecl;
124 }
125 
126 static bool DeduceTemplateArguments(ASTContext &Context, QualType Param,
127                                     QualType Arg,
128                              llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
129   // We only want to look at the canonical types, since typedefs and
130   // sugar are not part of template argument deduction.
131   Param = Context.getCanonicalType(Param);
132   Arg = Context.getCanonicalType(Arg);
133 
134   // If the parameter type is not dependent, just compare the types
135   // directly.
136   if (!Param->isDependentType())
137     return Param == Arg;
138 
139   // C++ [temp.deduct.type]p9:
140   //
141   //   A template type argument T, a template template argument TT or a
142   //   template non-type argument i can be deduced if P and A have one of
143   //   the following forms:
144   //
145   //     T
146   //     cv-list T
147   if (const TemplateTypeParmType *TemplateTypeParm
148         = Param->getAsTemplateTypeParmType()) {
149     // The argument type can not be less qualified than the parameter
150     // type.
151     if (Param.isMoreQualifiedThan(Arg))
152       return false;
153 
154     assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0");
155 
156     unsigned Quals = Arg.getCVRQualifiers() & ~Param.getCVRQualifiers();
157     QualType DeducedType = Arg.getQualifiedType(Quals);
158 	  unsigned Index = TemplateTypeParm->getIndex();
159 
160     if (Deduced[Index].isNull())
161       Deduced[Index] = TemplateArgument(SourceLocation(), DeducedType);
162     else {
163       // C++ [temp.deduct.type]p2:
164       //   [...] If type deduction cannot be done for any P/A pair, or if for
165       //   any pair the deduction leads to more than one possible set of
166       //   deduced values, or if different pairs yield different deduced
167       //   values, or if any template argument remains neither deduced nor
168       //   explicitly specified, template argument deduction fails.
169       if (Deduced[Index].getAsType() != DeducedType)
170         return false;
171     }
172     return true;
173   }
174 
175   if (Param.getCVRQualifiers() != Arg.getCVRQualifiers())
176     return false;
177 
178   switch (Param->getTypeClass()) {
179     // No deduction possible for these types
180     case Type::Builtin:
181       return false;
182 
183 
184     //     T *
185     case Type::Pointer: {
186       const PointerType *PointerArg = Arg->getAsPointerType();
187       if (!PointerArg)
188         return false;
189 
190       return DeduceTemplateArguments(Context,
191                                    cast<PointerType>(Param)->getPointeeType(),
192                                      PointerArg->getPointeeType(),
193                                      Deduced);
194     }
195 
196     //     T &
197     case Type::LValueReference: {
198       const LValueReferenceType *ReferenceArg = Arg->getAsLValueReferenceType();
199       if (!ReferenceArg)
200         return false;
201 
202       return DeduceTemplateArguments(Context,
203                            cast<LValueReferenceType>(Param)->getPointeeType(),
204                                      ReferenceArg->getPointeeType(),
205                                      Deduced);
206     }
207 
208     //     T && [C++0x]
209     case Type::RValueReference: {
210       const RValueReferenceType *ReferenceArg = Arg->getAsRValueReferenceType();
211       if (!ReferenceArg)
212         return false;
213 
214       return DeduceTemplateArguments(Context,
215                            cast<RValueReferenceType>(Param)->getPointeeType(),
216                                      ReferenceArg->getPointeeType(),
217                                      Deduced);
218     }
219 
220     //     T [] (implied, but not stated explicitly)
221     case Type::IncompleteArray: {
222       const IncompleteArrayType *IncompleteArrayArg =
223         Context.getAsIncompleteArrayType(Arg);
224       if (!IncompleteArrayArg)
225         return false;
226 
227       return DeduceTemplateArguments(Context,
228                      Context.getAsIncompleteArrayType(Param)->getElementType(),
229                                      IncompleteArrayArg->getElementType(),
230                                      Deduced);
231     }
232 
233     //     T [integer-constant]
234     case Type::ConstantArray: {
235       const ConstantArrayType *ConstantArrayArg =
236         Context.getAsConstantArrayType(Arg);
237       if (!ConstantArrayArg)
238         return false;
239 
240       const ConstantArrayType *ConstantArrayParm =
241         Context.getAsConstantArrayType(Param);
242       if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize())
243         return false;
244 
245       return DeduceTemplateArguments(Context,
246                                      ConstantArrayParm->getElementType(),
247                                      ConstantArrayArg->getElementType(),
248                                      Deduced);
249     }
250 
251     //     type [i]
252     case Type::DependentSizedArray: {
253       const ArrayType *ArrayArg = dyn_cast<ArrayType>(Arg);
254       if (!ArrayArg)
255         return false;
256 
257       // Check the element type of the arrays
258       const DependentSizedArrayType *DependentArrayParm
259         = cast<DependentSizedArrayType>(Param);
260       if (!DeduceTemplateArguments(Context,
261                                    DependentArrayParm->getElementType(),
262                                    ArrayArg->getElementType(),
263                                    Deduced))
264         return false;
265 
266       // Determine the array bound is something we can deduce.
267       NonTypeTemplateParmDecl *NTTP
268         = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr());
269       if (!NTTP)
270         return true;
271 
272       // We can perform template argument deduction for the given non-type
273       // template parameter.
274       assert(NTTP->getDepth() == 0 &&
275              "Cannot deduce non-type template argument at depth > 0");
276       if (const ConstantArrayType *ConstantArrayArg
277             = dyn_cast<ConstantArrayType>(ArrayArg))
278         return DeduceNonTypeTemplateArgument(Context, NTTP,
279                                              ConstantArrayArg->getSize(),
280                                              Deduced);
281       if (const DependentSizedArrayType *DependentArrayArg
282             = dyn_cast<DependentSizedArrayType>(ArrayArg))
283         return DeduceNonTypeTemplateArgument(Context, NTTP,
284                                              DependentArrayArg->getSizeExpr(),
285                                              Deduced);
286 
287       // Incomplete type does not match a dependently-sized array type
288       return false;
289     }
290 
291     //     type(*)(T)
292     //     T(*)()
293     //     T(*)(T)
294     case Type::FunctionProto: {
295       const FunctionProtoType *FunctionProtoArg =
296         dyn_cast<FunctionProtoType>(Arg);
297       if (!FunctionProtoArg)
298         return false;
299 
300       const FunctionProtoType *FunctionProtoParam =
301         cast<FunctionProtoType>(Param);
302 
303       if (FunctionProtoParam->getTypeQuals() !=
304           FunctionProtoArg->getTypeQuals())
305         return false;
306 
307       if (FunctionProtoParam->getNumArgs() != FunctionProtoArg->getNumArgs())
308         return false;
309 
310       if (FunctionProtoParam->isVariadic() != FunctionProtoArg->isVariadic())
311         return false;
312 
313       // Check return types.
314       if (!DeduceTemplateArguments(Context,
315                                    FunctionProtoParam->getResultType(),
316                                    FunctionProtoArg->getResultType(),
317                                    Deduced))
318         return false;
319 
320       for (unsigned I = 0, N = FunctionProtoParam->getNumArgs(); I != N; ++I) {
321         // Check argument types.
322         if (!DeduceTemplateArguments(Context,
323                                      FunctionProtoParam->getArgType(I),
324                                      FunctionProtoArg->getArgType(I),
325                                      Deduced))
326           return false;
327       }
328 
329       return true;
330     }
331 
332     //     template-name<T> (wheretemplate-name refers to a class template)
333     //     template-name<i>
334     //     TT<T> (TODO)
335     //     TT<i> (TODO)
336     //     TT<> (TODO)
337     case Type::TemplateSpecialization: {
338       const TemplateSpecializationType *SpecParam
339         = cast<TemplateSpecializationType>(Param);
340 
341       // Check whether the template argument is a dependent template-id.
342       // FIXME: This is untested code; it can be tested when we implement
343       // partial ordering of class template partial specializations.
344       if (const TemplateSpecializationType *SpecArg
345             = dyn_cast<TemplateSpecializationType>(Arg)) {
346         // Perform template argument deduction for the template name.
347         if (!DeduceTemplateArguments(Context,
348                                      SpecParam->getTemplateName(),
349                                      SpecArg->getTemplateName(),
350                                      Deduced))
351           return false;
352 
353         unsigned NumArgs = SpecParam->getNumArgs();
354 
355         // FIXME: When one of the template-names refers to a
356         // declaration with default template arguments, do we need to
357         // fill in those default template arguments here? Most likely,
358         // the answer is "yes", but I don't see any references. This
359         // issue may be resolved elsewhere, because we may want to
360         // instantiate default template arguments when
361         if (SpecArg->getNumArgs() != NumArgs)
362           return false;
363 
364         // Perform template argument deduction on each template
365         // argument.
366         for (unsigned I = 0; I != NumArgs; ++I)
367           if (!DeduceTemplateArguments(Context,
368                                        SpecParam->getArg(I),
369                                        SpecArg->getArg(I),
370                                        Deduced))
371             return false;
372 
373         return true;
374       }
375 
376       // If the argument type is a class template specialization, we
377       // perform template argument deduction using its template
378       // arguments.
379       const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
380       if (!RecordArg)
381         return false;
382 
383       ClassTemplateSpecializationDecl *SpecArg
384         = dyn_cast<ClassTemplateSpecializationDecl>(RecordArg->getDecl());
385       if (!SpecArg)
386         return false;
387 
388       // Perform template argument deduction for the template name.
389       if (!DeduceTemplateArguments(Context,
390                                    SpecParam->getTemplateName(),
391                                    TemplateName(SpecArg->getSpecializedTemplate()),
392                                    Deduced))
393           return false;
394 
395       // FIXME: Can the # of arguments in the parameter and the argument differ?
396       unsigned NumArgs = SpecParam->getNumArgs();
397       const TemplateArgumentList &ArgArgs = SpecArg->getTemplateArgs();
398       if (NumArgs != ArgArgs.size())
399         return false;
400 
401       for (unsigned I = 0; I != NumArgs; ++I)
402         if (!DeduceTemplateArguments(Context,
403                                      SpecParam->getArg(I),
404                                      ArgArgs.get(I),
405                                      Deduced))
406           return false;
407 
408       return true;
409     }
410 
411     //     T type::*
412     //     T T::*
413     //     T (type::*)()
414     //     type (T::*)()
415     //     type (type::*)(T)
416     //     type (T::*)(T)
417     //     T (type::*)(T)
418     //     T (T::*)()
419     //     T (T::*)(T)
420     case Type::MemberPointer: {
421       const MemberPointerType *MemPtrParam = cast<MemberPointerType>(Param);
422       const MemberPointerType *MemPtrArg = dyn_cast<MemberPointerType>(Arg);
423       if (!MemPtrArg)
424         return false;
425 
426       return DeduceTemplateArguments(Context,
427                                      MemPtrParam->getPointeeType(),
428                                      MemPtrArg->getPointeeType(),
429                                      Deduced) &&
430         DeduceTemplateArguments(Context,
431                                 QualType(MemPtrParam->getClass(), 0),
432                                 QualType(MemPtrArg->getClass(), 0),
433                                 Deduced);
434     }
435 
436     case Type::TypeOfExpr:
437     case Type::TypeOf:
438     case Type::Typename:
439       // No template argument deduction for these types
440       return true;
441 
442     default:
443       break;
444   }
445 
446   // FIXME: Many more cases to go (to go).
447   return false;
448 }
449 
450 static bool
451 DeduceTemplateArguments(ASTContext &Context, const TemplateArgument &Param,
452                         const TemplateArgument &Arg,
453                         llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
454   switch (Param.getKind()) {
455   case TemplateArgument::Null:
456     assert(false && "Null template argument in parameter list");
457     break;
458 
459   case TemplateArgument::Type:
460     assert(Arg.getKind() == TemplateArgument::Type && "Type/value mismatch");
461     return DeduceTemplateArguments(Context, Param.getAsType(),
462                                    Arg.getAsType(), Deduced);
463 
464   case TemplateArgument::Declaration:
465     // FIXME: Implement this check
466     assert(false && "Unimplemented template argument deduction case");
467     return false;
468 
469   case TemplateArgument::Integral:
470     if (Arg.getKind() == TemplateArgument::Integral) {
471       // FIXME: Zero extension + sign checking here?
472       return *Param.getAsIntegral() == *Arg.getAsIntegral();
473     }
474     if (Arg.getKind() == TemplateArgument::Expression)
475       return false;
476 
477     assert(false && "Type/value mismatch");
478     return false;
479 
480   case TemplateArgument::Expression: {
481     if (NonTypeTemplateParmDecl *NTTP
482           = getDeducedParameterFromExpr(Param.getAsExpr())) {
483       if (Arg.getKind() == TemplateArgument::Integral)
484         // FIXME: Sign problems here
485         return DeduceNonTypeTemplateArgument(Context, NTTP,
486                                              *Arg.getAsIntegral(), Deduced);
487       if (Arg.getKind() == TemplateArgument::Expression)
488         return DeduceNonTypeTemplateArgument(Context, NTTP, Arg.getAsExpr(),
489                                              Deduced);
490 
491       assert(false && "Type/value mismatch");
492       return false;
493     }
494 
495     // Can't deduce anything, but that's okay.
496     return true;
497   }
498   }
499 
500   return true;
501 }
502 
503 static bool
504 DeduceTemplateArguments(ASTContext &Context,
505                         const TemplateArgumentList &ParamList,
506                         const TemplateArgumentList &ArgList,
507                         llvm::SmallVectorImpl<TemplateArgument> &Deduced) {
508   assert(ParamList.size() == ArgList.size());
509   for (unsigned I = 0, N = ParamList.size(); I != N; ++I) {
510     if (!DeduceTemplateArguments(Context, ParamList[I], ArgList[I], Deduced))
511       return false;
512   }
513   return true;
514 }
515 
516 
517 TemplateArgumentList *
518 Sema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial,
519                               const TemplateArgumentList &TemplateArgs) {
520   // Deduce the template arguments for the partial specialization
521   llvm::SmallVector<TemplateArgument, 4> Deduced;
522   Deduced.resize(Partial->getTemplateParameters()->size());
523   if (! ::DeduceTemplateArguments(Context, Partial->getTemplateArgs(),
524                                   TemplateArgs, Deduced))
525     return 0;
526 
527   // FIXME: It isn't clear whether we want the diagnostic to point at
528   // the partial specialization itself or at the actual point of
529   // instantiation.
530   InstantiatingTemplate Inst(*this, Partial->getLocation(), Partial,
531                              Deduced.data(), Deduced.size());
532   if (Inst)
533     return 0;
534 
535   // C++ [temp.deduct.type]p2:
536   //   [...] or if any template argument remains neither deduced nor
537   //   explicitly specified, template argument deduction fails.
538   TemplateArgumentListBuilder Builder(Context);
539   for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
540     if (Deduced[I].isNull())
541       return 0;
542 
543     Builder.push_back(Deduced[I]);
544   }
545 
546   // Form the template argument list from the deduced template arguments.
547   TemplateArgumentList *DeducedArgumentList
548     = new (Context) TemplateArgumentList(Context, Builder, /*CopyArgs=*/true,
549                                          /*FlattenArgs=*/true);
550 
551   // Now that we have all of the deduced template arguments, take
552   // another pass through them to convert any integral template
553   // arguments to the appropriate type.
554   for (unsigned I = 0, N = Deduced.size(); I != N; ++I) {
555     TemplateArgument &Arg = Deduced[I];
556     if (Arg.getKind() == TemplateArgument::Integral) {
557       const NonTypeTemplateParmDecl *Parm
558         = cast<NonTypeTemplateParmDecl>(Partial->getTemplateParameters()
559                                           ->getParam(I));
560       QualType T = InstantiateType(Parm->getType(), *DeducedArgumentList,
561                                    Parm->getLocation(), Parm->getDeclName());
562       if (T.isNull()) // FIXME: DeducedArgumentList->Destroy(Context);
563         return 0;
564 
565       // FIXME: Make sure we didn't overflow our data type!
566       llvm::APSInt &Value = *Arg.getAsIntegral();
567       unsigned AllowedBits = Context.getTypeSize(T);
568       if (Value.getBitWidth() != AllowedBits)
569         Value.extOrTrunc(AllowedBits);
570       Value.setIsSigned(T->isSignedIntegerType());
571       Arg.setIntegralType(T);
572     }
573 
574     (*DeducedArgumentList)[I] = Arg;
575   }
576 
577   // Substitute the deduced template arguments into the template
578   // arguments of the class template partial specialization, and
579   // verify that the instantiated template arguments are both valid
580   // and are equivalent to the template arguments originally provided
581   // to the class template.
582   ClassTemplateDecl *ClassTemplate = Partial->getSpecializedTemplate();
583   const TemplateArgumentList &PartialTemplateArgs = Partial->getTemplateArgs();
584   for (unsigned I = 0, N = PartialTemplateArgs.flat_size(); I != N; ++I) {
585     TemplateArgument InstArg = Instantiate(PartialTemplateArgs[I],
586                                            *DeducedArgumentList);
587     if (InstArg.isNull()) {
588       // FIXME: DeducedArgumentList->Destroy(Context); (or use RAII)
589       return 0;
590     }
591 
592     Decl *Param
593       = const_cast<Decl *>(ClassTemplate->getTemplateParameters()->getParam(I));
594     if (isa<TemplateTypeParmDecl>(Param)) {
595       if (InstArg.getKind() != TemplateArgument::Type ||
596           Context.getCanonicalType(InstArg.getAsType())
597             != Context.getCanonicalType(TemplateArgs[I].getAsType()))
598         // FIXME: DeducedArgumentList->Destroy(Context); (or use RAII)
599         return 0;
600     } else if (NonTypeTemplateParmDecl *NTTP
601                  = dyn_cast<NonTypeTemplateParmDecl>(Param)) {
602       QualType T = InstantiateType(NTTP->getType(), TemplateArgs,
603                                    NTTP->getLocation(), NTTP->getDeclName());
604       if (T.isNull())
605         // FIXME: DeducedArgumentList->Destroy(Context); (or use RAII)
606         return 0;
607 
608       if (InstArg.getKind() == TemplateArgument::Declaration ||
609           InstArg.getKind() == TemplateArgument::Expression) {
610         // Turn the template argument into an expression, so that we can
611         // perform type checking on it and convert it to the type of the
612         // non-type template parameter. FIXME: Will this expression be
613         // leaked? It's hard to tell, since our ownership model for
614         // expressions in template arguments is so poor.
615         Expr *E = 0;
616         if (InstArg.getKind() == TemplateArgument::Declaration) {
617           NamedDecl *D = cast<NamedDecl>(InstArg.getAsDecl());
618           QualType T = Context.OverloadTy;
619           if (ValueDecl *VD = dyn_cast<ValueDecl>(D))
620             T = VD->getType().getNonReferenceType();
621           E = new (Context) DeclRefExpr(D, T, InstArg.getLocation());
622         } else {
623           E = InstArg.getAsExpr();
624         }
625 
626         // Check that the template argument can be used to initialize
627         // the corresponding template parameter.
628         if (CheckTemplateArgument(NTTP, T, E, InstArg))
629           return 0;
630       }
631 
632       switch (InstArg.getKind()) {
633       case TemplateArgument::Null:
634         assert(false && "Null template arguments cannot get here");
635         return 0;
636 
637       case TemplateArgument::Type:
638         assert(false && "Type/value mismatch");
639         return 0;
640 
641       case TemplateArgument::Integral: {
642         llvm::APSInt &Value = *InstArg.getAsIntegral();
643         if (T->isIntegralType() || T->isEnumeralType()) {
644           QualType IntegerType = Context.getCanonicalType(T);
645           if (const EnumType *Enum = dyn_cast<EnumType>(IntegerType))
646             IntegerType = Context.getCanonicalType(
647                                            Enum->getDecl()->getIntegerType());
648 
649           // Check that an unsigned parameter does not receive a negative
650           // value.
651           if (IntegerType->isUnsignedIntegerType()
652               && (Value.isSigned() && Value.isNegative()))
653             return 0;
654 
655           // Check for truncation. If the number of bits in the
656           // instantiated template argument exceeds what is allowed by
657           // the type, template argument deduction fails.
658           unsigned AllowedBits = Context.getTypeSize(IntegerType);
659           if (Value.getActiveBits() > AllowedBits)
660             return 0;
661 
662           if (Value.getBitWidth() != AllowedBits)
663             Value.extOrTrunc(AllowedBits);
664           Value.setIsSigned(IntegerType->isSignedIntegerType());
665 
666           // Check that the instantiated value is the same as the
667           // value provided as a template argument.
668           if (Value != *TemplateArgs[I].getAsIntegral())
669             return 0;
670         } else if (T->isPointerType() || T->isMemberPointerType()) {
671           // Deal with NULL pointers that are used to initialize
672           // pointer and pointer-to-member non-type template
673           // parameters (C++0x).
674           if (TemplateArgs[I].getAsDecl())
675             return 0; // Not a NULL declaration
676 
677           // Check that the integral value is 0, the NULL pointer
678           // constant.
679           if (Value != 0)
680             return 0;
681         } else
682           return 0;
683         break;
684       }
685 
686       case TemplateArgument::Declaration:
687         if (Context.getCanonicalDecl(InstArg.getAsDecl())
688               != Context.getCanonicalDecl(TemplateArgs[I].getAsDecl()))
689           return 0;
690         break;
691 
692       case TemplateArgument::Expression:
693         // FIXME: Check equality of expressions
694         break;
695       }
696     } else {
697       assert(isa<TemplateTemplateParmDecl>(Param));
698       // FIXME: Check template template arguments
699     }
700   }
701 
702   return DeducedArgumentList;
703 }
704