[Sema] Disallow ambiguous base-to-derived conversion in template argument deduction

[erik.pilkington]

Summary

Previously, Clang would incorrectly accept the following:

template<int N> struct A {};
struct B : A<0>, A<1> {};
template<int N> int f(A<N>);
int main() { f(B()); }

The problem is that when considering the base classes of B, there are 2 possible ambiguous bases that could be deduced. Therefore, deduction ought to fail (temp.deduct.call p5).

There are 3 improvements that I want to make here as well:

1. Introduce a TDK_AmbiguousBaseClasses so that this diagnostic isn't terrible.
2. Reapply Richard's r267453, (with some modifications) which previously broke stdlibc++'s tuple implementation (PR27601, reverted in r270016). This refactors the handmade base class traversal I fixed here to instead use CXXRecordDecl::forallBases(), I believe that requiring matching number of arguments in the DeduceTemplateArguments at SemaTemplateDeduction.cpp:433 will fix it.
3. A NFC patch to rename the 10 (!) overloads of DeduceTemplateArguments to have more descriptive names. These functions are *really* annoying to deal with because of that.

If it would be better to do a subset (or all) of these improvements here, I could always update the diff. Fixes PR28195.

Thanks!

[rsmith]

Please also add the testcase from PR27601.

[erik.pilkington]

Do you mean Faisal's example? He committed that in r270016.
Thanks for taking a look!

[rsmith]

Well OK then, commit away! :)

cfe/trunk/lib/Sema/SemaTemplateDeduction.cpp

DeduceTemplateArgumentsByTypeMatch(Sema &S,
                                    QualType Arg,
                                    TemplateDeductionInfo &Info,
                                    SmallVectorImpl<DeducedTemplateArgument> &
                                                       Deduced,
                                    unsigned TDF,
                                    bool PartialOrdering = false);
 
 static Sema::TemplateDeductionResult
-DeduceTemplateArguments(Sema &S,
-                        TemplateParameterList *TemplateParams,
+DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,
                         const TemplateArgument *Params, unsigned NumParams,
                         const TemplateArgument *Args, unsigned NumArgs,
                         TemplateDeductionInfo &Info,
-                        SmallVectorImpl<DeducedTemplateArgument> &Deduced);
+                        SmallVectorImpl<DeducedTemplateArgument> &Deduced,
+                        bool NumberOfArgumentsMustMatch);
 
 /// \brief If the given expression is of a form that permits the deduction
 /// of a non-type template parameter, return the declaration of that
 /// non-type template parameter.
 static NonTypeTemplateParmDecl *getDeducedParameterFromExpr(Expr *E) {
   // If we are within an alias template, the expression may have undergone
   // any number of parameter substitutions already.
   while (1) {
if (Sema::TemplateDeductionResult Result
                                     SpecArg->getTemplateName(),
                                     Info, Deduced))
       return Result;
 
 
     // Perform template argument deduction on each template
     // argument. Ignore any missing/extra arguments, since they could be
     // filled in by default arguments.
-    return DeduceTemplateArguments(S, TemplateParams,
-                                   Param->getArgs(), Param->getNumArgs(),
-                                   SpecArg->getArgs(), SpecArg->getNumArgs(),
-                                   Info, Deduced);
+    return DeduceTemplateArguments(S, TemplateParams, Param->getArgs(),
+                                   Param->getNumArgs(), SpecArg->getArgs(),
+                                   SpecArg->getNumArgs(), Info, Deduced,
+                                   /*NumberOfArgumentsMustMatch=*/false);
   }
 
   // If the argument type is a class template specialization, we
   // perform template argument deduction using its template
   // arguments.
   const RecordType *RecordArg = dyn_cast<RecordType>(Arg);
   if (!RecordArg) {
     Info.FirstArg = TemplateArgument(QualType(Param, 0));
if (Sema::TemplateDeductionResult Result
         = DeduceTemplateArguments(S,
                                   TemplateParams,
                                   Param->getTemplateName(),
                                TemplateName(SpecArg->getSpecializedTemplate()),
                                   Info, Deduced))
     return Result;
 
   // Perform template argument deduction for the template arguments.
-  return DeduceTemplateArguments(S, TemplateParams,
-                                 Param->getArgs(), Param->getNumArgs(),
-                                 SpecArg->getTemplateArgs().data(),
-                                 SpecArg->getTemplateArgs().size(),
-                                 Info, Deduced);
+  return DeduceTemplateArguments(
+      S, TemplateParams, Param->getArgs(), Param->getNumArgs(),
+      SpecArg->getTemplateArgs().data(), SpecArg->getTemplateArgs().size(),
+      Info, Deduced, /*NumberOfArgumentsMustMatch=*/true);
 }
 
 /// \brief Determines whether the given type is an opaque type that
 /// might be more qualified when instantiated.
 static bool IsPossiblyOpaquelyQualifiedType(QualType T) {
   switch (T->getTypeClass()) {
   case Type::TypeOfExpr:
   case Type::TypeOf:
case Type::TemplateSpecialization: {
 
       // Use data recursion to crawl through the list of base classes.
       // Visited contains the set of nodes we have already visited, while
       // ToVisit is our stack of records that we still need to visit.
       llvm::SmallPtrSet<const RecordType *, 8> Visited;
       SmallVector<const RecordType *, 8> ToVisit;
       ToVisit.push_back(RecordT);
       bool Successful = false;
+      SmallVector<DeducedTemplateArgument, 8> SuccessfulDeduced;
       while (!ToVisit.empty()) {
         // Retrieve the next class in the inheritance hierarchy.
         const RecordType *NextT = ToVisit.pop_back_val();
 
         // If we have already seen this type, skip it.
         if (!Visited.insert(NextT).second)
           continue;
 
         // If this is a base class, try to perform template argument
         // deduction from it.
         if (NextT != RecordT) {
           TemplateDeductionInfo BaseInfo(Info.getLocation());
           Sema::TemplateDeductionResult BaseResult =
               DeduceTemplateArguments(S, TemplateParams, SpecParam,
                                       QualType(NextT, 0), BaseInfo, Deduced);
 
           // If template argument deduction for this base was successful,
           // note that we had some success. Otherwise, ignore any deductions
           // from this base class.
           if (BaseResult == Sema::TDK_Success) {
+            // If we've already seen some success, then deduction fails due to
+            // an ambiguity (temp.deduct.call p5).
+            if (Successful)
+              return Sema::TDK_MiscellaneousDeductionFailure;
+
             Successful = true;
-            DeducedOrig.clear();
-            DeducedOrig.append(Deduced.begin(), Deduced.end());
+            std::swap(SuccessfulDeduced, Deduced);
+
             Info.Param = BaseInfo.Param;
             Info.FirstArg = BaseInfo.FirstArg;
             Info.SecondArg = BaseInfo.SecondArg;
-          } else
-            Deduced = DeducedOrig;
+          }
+
         }
 
         // Visit base classes
         CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
         for (const auto &Base : Next->bases()) {
           assert(Base.getType()->isRecordType() &&
                  "Base class that isn't a record?");
           ToVisit.push_back(Base.getType()->getAs<RecordType>());
         }
       }
 
-      if (Successful)
+      if (Successful) {
+        std::swap(SuccessfulDeduced, Deduced);
         return Sema::TDK_Success;
+      }
 
       return Result;
     }
 
     //     T type::*
     //     T T::*
     //     T (type::*)()
     //     type (T::*)()
while (ArgIdx < NumArgs) {
     if (Arg.isPackExpansion())
       return true;
   }
 
   return false;
 }
 
 static Sema::TemplateDeductionResult
-DeduceTemplateArguments(Sema &S,
-                        TemplateParameterList *TemplateParams,
+DeduceTemplateArguments(Sema &S, TemplateParameterList *TemplateParams,
                         const TemplateArgument *Params, unsigned NumParams,
                         const TemplateArgument *Args, unsigned NumArgs,
                         TemplateDeductionInfo &Info,
-                        SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
+                        SmallVectorImpl<DeducedTemplateArgument> &Deduced,
+                        bool NumberOfArgumentsMustMatch) {
   // C++0x [temp.deduct.type]p9:
   //   If the template argument list of P contains a pack expansion that is not
   //   the last template argument, the entire template argument list is a
   //   non-deduced context.
   if (hasPackExpansionBeforeEnd(Params, NumParams))
     return Sema::TDK_Success;
 
   // C++0x [temp.deduct.type]p9:
   //   If P has a form that contains <T> or <i>, then each argument Pi of the
   //   respective template argument list P is compared with the corresponding
   //   argument Ai of the corresponding template argument list of A.
   unsigned ArgIdx = 0, ParamIdx = 0;
   for (; hasTemplateArgumentForDeduction(Params, ParamIdx, NumParams);
        ++ParamIdx) {
     if (!Params[ParamIdx].isPackExpansion()) {
       // The simple case: deduce template arguments by matching Pi and Ai.
 
       // Check whether we have enough arguments.
       if (!hasTemplateArgumentForDeduction(Args, ArgIdx, NumArgs))
-        return Sema::TDK_Success;
+        return NumberOfArgumentsMustMatch ? Sema::TDK_TooFewArguments
+                                          : Sema::TDK_Success;
 
       if (Args[ArgIdx].isPackExpansion()) {
         // FIXME: We follow the logic of C++0x [temp.deduct.type]p22 here,
         // but applied to pack expansions that are template arguments.
         return Sema::TDK_MiscellaneousDeductionFailure;
       }
 
       // Perform deduction for this Pi/Ai pair.
DeduceTemplateArguments(Sema &S,
                         TemplateParameterList *TemplateParams,
                         const TemplateArgumentList &ParamList,
                         const TemplateArgumentList &ArgList,
                         TemplateDeductionInfo &Info,
                         SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
   return DeduceTemplateArguments(S, TemplateParams,
                                  ParamList.data(), ParamList.size(),
                                  ArgList.data(), ArgList.size(),
-                                 Info, Deduced);
+                                 Info, Deduced, false);
 }
 
 /// \brief Determine whether two template arguments are the same.
 static bool isSameTemplateArg(ASTContext &Context,
                               const TemplateArgument &X,
                               const TemplateArgument &Y) {
   if (X.getKind() != Y.getKind())
     return false;

cfe/trunk/test/CXX/temp/temp.fct.spec/temp.deduct/temp.deduct.call/p3.cpp

 template<class T> void Foo(D<T, 1>);
 
 int fn() {
   D<D<B, 1>, 0> f;
   Foo(f);
 }
 
 }
+
+namespace PR28195 {
+
+template<int N> struct B {};
+struct D : B<0>, B<1> {};
+
+template<int N> int callee(B<N>); // expected-note{{failed template argument deduction}}
+
+int caller() {
+  callee(D()); // expected-error{{no matching function}}
+}
+
+}