SemaTemplateDeduction.cpp revision 199d99192fbcca9f043596c40ead4afab4999dba
10b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor//===------- SemaTemplateDeduction.cpp - Template Argument Deduction ------===/ 20b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor// 30b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor// The LLVM Compiler Infrastructure 40b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor// 50b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor// This file is distributed under the University of Illinois Open Source 60b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor// License. See LICENSE.TXT for details. 70b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor//===----------------------------------------------------------------------===/ 80b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor// 90b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor// This file implements C++ template argument deduction. 100b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor// 110b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor//===----------------------------------------------------------------------===/ 120b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 130b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor#include "Sema.h" 140b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor#include "clang/AST/ASTContext.h" 150b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor#include "clang/AST/DeclTemplate.h" 160b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor#include "clang/AST/StmtVisitor.h" 170b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor#include "clang/AST/Expr.h" 180b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor#include "clang/AST/ExprCXX.h" 190b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor#include "clang/Parse/DeclSpec.h" 200b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor#include "llvm/Support/Compiler.h" 210b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregorusing namespace clang; 220b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 23199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor/// \brief If the given expression is of a form that permits the deduction 24199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor/// of a non-type template parameter, return the declaration of that 25199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor/// non-type template parameter. 26199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregorstatic NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) { 27199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (ImplicitCastExpr *IC = dyn_cast<ImplicitCastExpr>(E)) 28199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor E = IC->getSubExpr(); 29199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 30199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E)) 31199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return dyn_cast<NonTypeTemplateParmDecl>(DRE->getDecl()); 32199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 33199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return 0; 34199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor} 35199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 36199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor/// \brief Deduce the value of the given non-type template parameter 37199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor/// from the given constant. 38199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor/// 39199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor/// \returns true if deduction succeeded, false otherwise. 40199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregorstatic bool DeduceNonTypeTemplateArgument(ASTContext &Context, 41199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor NonTypeTemplateParmDecl *NTTP, 42199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor llvm::APInt Value, 43199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 44199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor assert(NTTP->getDepth() == 0 && 45199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor "Cannot deduce non-type template argument with depth > 0"); 46199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 47199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (Deduced[NTTP->getIndex()].isNull()) { 48199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor Deduced[NTTP->getIndex()] = TemplateArgument(SourceLocation(), 49199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor llvm::APSInt(Value), 50199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor NTTP->getType()); 51199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return true; 52199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor } 53199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 54199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (Deduced[NTTP->getIndex()].getKind() != TemplateArgument::Integral) 55199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return false; 56199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 57199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // If the template argument was previously deduced to a negative value, 58199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // then our deduction fails. 59199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor const llvm::APSInt *PrevValuePtr = Deduced[NTTP->getIndex()].getAsIntegral(); 60199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor assert(PrevValuePtr && "Not an integral template argument?"); 61199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (PrevValuePtr->isSigned() && PrevValuePtr->isNegative()) 62199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return false; 63199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 64199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor llvm::APInt PrevValue = *PrevValuePtr; 65199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (Value.getBitWidth() > PrevValue.getBitWidth()) 66199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor PrevValue.zext(Value.getBitWidth()); 67199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor else if (Value.getBitWidth() < PrevValue.getBitWidth()) 68199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor Value.zext(PrevValue.getBitWidth()); 69199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return Value == PrevValue; 70199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor} 71199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 72199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor/// \brief Deduce the value of the given non-type template parameter 73199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor/// from the given type- or value-dependent expression. 74199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor/// 75199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor/// \returns true if deduction succeeded, false otherwise. 76199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 77199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregorstatic bool DeduceNonTypeTemplateArgument(ASTContext &Context, 78199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor NonTypeTemplateParmDecl *NTTP, 79199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor Expr *Value, 80199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 81199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor assert(NTTP->getDepth() == 0 && 82199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor "Cannot deduce non-type template argument with depth > 0"); 83199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor assert((Value->isTypeDependent() || Value->isValueDependent()) && 84199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor "Expression template argument must be type- or value-dependent."); 85199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 86199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (Deduced[NTTP->getIndex()].isNull()) { 87199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // FIXME: Clone the Value? 88199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor Deduced[NTTP->getIndex()] = TemplateArgument(Value); 89199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return true; 90199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor } 91199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 92199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (Deduced[NTTP->getIndex()].getKind() == TemplateArgument::Integral) { 93199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // Okay, we deduced a constant in one case and a dependent expression 94199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // in another case. FIXME: Later, we will check that instantiating the 95199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // dependent expression gives us the constant value. 96199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return true; 97199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor } 98199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 99199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // FIXME: Compare the expressions for equality! 100199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return true; 101199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor} 102199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 1030b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregorstatic bool DeduceTemplateArguments(ASTContext &Context, QualType Param, 1040b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor QualType Arg, 1050b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 1060b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // We only want to look at the canonical types, since typedefs and 1070b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // sugar are not part of template argument deduction. 1080b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor Param = Context.getCanonicalType(Param); 1090b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor Arg = Context.getCanonicalType(Arg); 1100b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 1110b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // If the parameter type is not dependent, just compare the types 1120b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // directly. 1130b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor if (!Param->isDependentType()) 1140b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor return Param == Arg; 1150b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 116199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // C++ [temp.deduct.type]p9: 117199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // 118199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // A template type argument T, a template template argument TT or a 119199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // template non-type argument i can be deduced if P and A have one of 120199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // the following forms: 121199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // 122199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // T 123199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // cv-list T 1240b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor if (const TemplateTypeParmType *TemplateTypeParm 1250b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor = Param->getAsTemplateTypeParmType()) { 1260b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // The argument type can not be less qualified than the parameter 1270b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // type. 1280b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor if (Param.isMoreQualifiedThan(Arg)) 1290b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor return false; 1300b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 1310b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor assert(TemplateTypeParm->getDepth() == 0 && "Can't deduce with depth > 0"); 1320b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 1330b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor unsigned Quals = Arg.getCVRQualifiers() & ~Param.getCVRQualifiers(); 1340b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor QualType DeducedType = Arg.getQualifiedType(Quals); 1350b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor unsigned Index = TemplateTypeParm->getIndex(); 1360b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 1370b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor if (Deduced[Index].isNull()) 1380b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor Deduced[Index] = TemplateArgument(SourceLocation(), DeducedType); 1390b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor else { 1400b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // C++ [temp.deduct.type]p2: 1410b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // [...] If type deduction cannot be done for any P/A pair, or if for 1420b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // any pair the deduction leads to more than one possible set of 1430b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // deduced values, or if different pairs yield different deduced 1440b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // values, or if any template argument remains neither deduced nor 1450b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // explicitly specified, template argument deduction fails. 1460b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor if (Deduced[Index].getAsType() != DeducedType) 1470b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor return false; 1480b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor } 1490b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor return true; 1500b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor } 1510b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 1520b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor if (Param.getCVRQualifiers() != Arg.getCVRQualifiers()) 1530b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor return false; 1540b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 155d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor switch (Param->getTypeClass()) { 156199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // No deduction possible for these types 157199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor case Type::Builtin: 158199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return false; 159199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 160199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 161199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // T * 162d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor case Type::Pointer: { 163d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor const PointerType *PointerArg = Arg->getAsPointerType(); 164d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor if (!PointerArg) 165d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor return false; 166d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor 167d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor return DeduceTemplateArguments(Context, 168d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor cast<PointerType>(Param)->getPointeeType(), 169d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor PointerArg->getPointeeType(), 170d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor Deduced); 171d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor } 172d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor 173199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // T & 174d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor case Type::LValueReference: { 175d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor const LValueReferenceType *ReferenceArg = Arg->getAsLValueReferenceType(); 176d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor if (!ReferenceArg) 177d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor return false; 178d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor 179d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor return DeduceTemplateArguments(Context, 180d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor cast<LValueReferenceType>(Param)->getPointeeType(), 181d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor ReferenceArg->getPointeeType(), 182d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor Deduced); 183d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor } 1840b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 185199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // T && [C++0x] 186d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor case Type::RValueReference: { 187d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor const RValueReferenceType *ReferenceArg = Arg->getAsRValueReferenceType(); 188d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor if (!ReferenceArg) 189d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor return false; 190d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor 191d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor return DeduceTemplateArguments(Context, 192d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor cast<RValueReferenceType>(Param)->getPointeeType(), 193d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor ReferenceArg->getPointeeType(), 194d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor Deduced); 195d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor } 196d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor 197199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // T [] (implied, but not stated explicitly) 1984d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson case Type::IncompleteArray: { 1994d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson const IncompleteArrayType *IncompleteArrayArg = 2004d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson Context.getAsIncompleteArrayType(Arg); 2014d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson if (!IncompleteArrayArg) 2024d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson return false; 2034d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson 2044d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson return DeduceTemplateArguments(Context, 2054d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson Context.getAsIncompleteArrayType(Param)->getElementType(), 2064d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson IncompleteArrayArg->getElementType(), 2074d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson Deduced); 2084d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson } 209199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 210199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // T [integer-constant] 2114d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson case Type::ConstantArray: { 2124d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson const ConstantArrayType *ConstantArrayArg = 2134d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson Context.getAsConstantArrayType(Arg); 2144d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson if (!ConstantArrayArg) 2154d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson return false; 2164d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson 2174d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson const ConstantArrayType *ConstantArrayParm = 2184d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson Context.getAsConstantArrayType(Param); 2194d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson if (ConstantArrayArg->getSize() != ConstantArrayParm->getSize()) 2204d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson return false; 2214d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson 2224d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson return DeduceTemplateArguments(Context, 2234d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson ConstantArrayParm->getElementType(), 2244d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson ConstantArrayArg->getElementType(), 2254d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson Deduced); 2264d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson } 2274d6fb501ffc0568ca5ca7266005e96a6f1273845Anders Carlsson 228199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // type [i] 229199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor case Type::DependentSizedArray: { 230199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor const ArrayType *ArrayArg = dyn_cast<ArrayType>(Arg); 231199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (!ArrayArg) 232199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return false; 233199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 234199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // Check the element type of the arrays 235199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor const DependentSizedArrayType *DependentArrayParm 236199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor = cast<DependentSizedArrayType>(Param); 237199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (!DeduceTemplateArguments(Context, 238199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor DependentArrayParm->getElementType(), 239199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor ArrayArg->getElementType(), 240199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor Deduced)) 241199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return false; 242199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 243199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // Determine the array bound is something we can deduce. 244199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor NonTypeTemplateParmDecl *NTTP 245199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor = getDeducedParameterFromExpr(DependentArrayParm->getSizeExpr()); 246199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (!NTTP) 247199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return true; 248199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 249199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // We can perform template argument deduction for the given non-type 250199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // template parameter. 251199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor assert(NTTP->getDepth() == 0 && 252199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor "Cannot deduce non-type template argument at depth > 0"); 253199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (const ConstantArrayType *ConstantArrayArg 254199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor = dyn_cast<ConstantArrayType>(ArrayArg)) 255199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return DeduceNonTypeTemplateArgument(Context, NTTP, 256199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor ConstantArrayArg->getSize(), 257199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor Deduced); 258199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (const DependentSizedArrayType *DependentArrayArg 259199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor = dyn_cast<DependentSizedArrayType>(ArrayArg)) 260199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return DeduceNonTypeTemplateArgument(Context, NTTP, 261199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor DependentArrayArg->getSizeExpr(), 262199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor Deduced); 263199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 264199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // Incomplete type does not match a dependently-sized array type 265199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return false; 266199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor } 267199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 268d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor default: 269d560d5025a0e5b1942d99d5f39005337b03a64c2Douglas Gregor break; 2700b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor } 2710b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 2720b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor // FIXME: Many more cases to go (to go). 2730b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor return false; 2740b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor} 2750b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 2760b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregorstatic bool 2770b9247f129401b4849682b2e2bcdea8fc977068aDouglas GregorDeduceTemplateArguments(ASTContext &Context, const TemplateArgument &Param, 2780b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor const TemplateArgument &Arg, 2790b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 2800b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor switch (Param.getKind()) { 281199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor case TemplateArgument::Null: 282199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor assert(false && "Null template argument in parameter list"); 283199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor break; 284199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 2850b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor case TemplateArgument::Type: 286199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor assert(Arg.getKind() == TemplateArgument::Type && "Type/value mismatch"); 2870b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor return DeduceTemplateArguments(Context, Param.getAsType(), 2880b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor Arg.getAsType(), Deduced); 2890b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 290199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor case TemplateArgument::Declaration: 291199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // FIXME: Implement this check 292199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor assert(false && "Unimplemented template argument deduction case"); 2930b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor return false; 294199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 295199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor case TemplateArgument::Integral: 296199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (Arg.getKind() == TemplateArgument::Integral) { 297199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // FIXME: Zero extension + sign checking here? 298199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return *Param.getAsIntegral() == *Arg.getAsIntegral(); 299199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor } 300199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (Arg.getKind() == TemplateArgument::Expression) 301199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return false; 302199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 303199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor assert(false && "Type/value mismatch"); 304199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return false; 305199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 306199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor case TemplateArgument::Expression: { 307199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (NonTypeTemplateParmDecl *NTTP 308199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor = getDeducedParameterFromExpr(Param.getAsExpr())) { 309199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (Arg.getKind() == TemplateArgument::Integral) 310199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // FIXME: Sign problems here 311199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return DeduceNonTypeTemplateArgument(Context, NTTP, 312199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor *Arg.getAsIntegral(), Deduced); 313199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (Arg.getKind() == TemplateArgument::Expression) 314199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return DeduceNonTypeTemplateArgument(Context, NTTP, Arg.getAsExpr(), 315199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor Deduced); 316199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 317199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor assert(false && "Type/value mismatch"); 318199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return false; 319199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor } 320199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 321199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // Can't deduce anything, but that's okay. 322199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return true; 323199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor } 3240b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor } 325199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 326199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return true; 3270b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor} 3280b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 3290b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregorstatic bool 3300b9247f129401b4849682b2e2bcdea8fc977068aDouglas GregorDeduceTemplateArguments(ASTContext &Context, 3310b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor const TemplateArgumentList &ParamList, 3320b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor const TemplateArgumentList &ArgList, 3330b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor llvm::SmallVectorImpl<TemplateArgument> &Deduced) { 3340b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor assert(ParamList.size() == ArgList.size()); 3350b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor for (unsigned I = 0, N = ParamList.size(); I != N; ++I) { 3360b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor if (!DeduceTemplateArguments(Context, ParamList[I], ArgList[I], Deduced)) 3370b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor return false; 3380b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor } 3390b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor return true; 3400b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor} 3410b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 3420b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor 343199d99192fbcca9f043596c40ead4afab4999dbaDouglas GregorTemplateArgumentList * 3440b9247f129401b4849682b2e2bcdea8fc977068aDouglas GregorSema::DeduceTemplateArguments(ClassTemplatePartialSpecializationDecl *Partial, 3450b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor const TemplateArgumentList &TemplateArgs) { 346199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // Deduce the template arguments for the partial specialization 3470b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor llvm::SmallVector<TemplateArgument, 4> Deduced; 3480b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor Deduced.resize(Partial->getTemplateParameters()->size()); 349199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (! ::DeduceTemplateArguments(Context, Partial->getTemplateArgs(), 350199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor TemplateArgs, Deduced)) 351199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return 0; 352199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 353199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // FIXME: Substitute the deduced template arguments into the template 354199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // arguments of the class template partial specialization; the resulting 355199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // template arguments should match TemplateArgs exactly. 356199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 357199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor for (unsigned I = 0, N = Deduced.size(); I != N; ++I) { 358199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor TemplateArgument &Arg = Deduced[I]; 359199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 360199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // FIXME: If this template argument was not deduced, but the corresponding 361199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // template parameter has a default argument, instantiate the default 362199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // argument. 363199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (Arg.isNull()) // FIXME: Result->Destroy(Context); 364199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return 0; 365199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 366199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (Arg.getKind() == TemplateArgument::Integral) { 367199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // FIXME: Instantiate the type, but we need some context! 368199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor const NonTypeTemplateParmDecl *Parm 369199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor = cast<NonTypeTemplateParmDecl>(Partial->getTemplateParameters() 370199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor ->getParam(I)); 371199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // QualType T = InstantiateType(Parm->getType(), *Result, 372199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // Parm->getLocation(), Parm->getDeclName()); 373199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // if (T.isNull()) // FIXME: Result->Destroy(Context); 374199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // return 0; 375199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor QualType T = Parm->getType(); 376199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 377199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor // FIXME: Make sure we didn't overflow our data type! 378199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor llvm::APSInt &Value = *Arg.getAsIntegral(); 379199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor unsigned AllowedBits = Context.getTypeSize(T); 380199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor if (Value.getBitWidth() != AllowedBits) 381199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor Value.extOrTrunc(AllowedBits); 382199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor Value.setIsSigned(T->isSignedIntegerType()); 383199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor Arg.setIntegralType(T); 384199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor } 385199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor } 386199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor 387199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor return new (Context) TemplateArgumentList(Context, Deduced.data(), 388199d99192fbcca9f043596c40ead4afab4999dbaDouglas Gregor Deduced.size(), /*CopyArgs=*/true); 3890b9247f129401b4849682b2e2bcdea8fc977068aDouglas Gregor} 390