[Sema] Improve overload resolution

[Mordante]

Summary

The overload resolution for initializer lists was incomplete. It did not
properly take the number of elements in the target array into account. The
size comparison already allows for an array of unknown boud, per P0338 'Permit
conversions to arrays of unknown bound'. However currently this is dead code.

This fixes the overload resolution for cases like:

void f(int(&&)[2]);

void g() {
  f({1});
  f({1, 2});
  f({1, 2, 3});
}

The patch adds extra members to ImplicitConversionSequence, making it larger
for members only used for an initializer list. The largest member of the class'
union is UserDefinedConversion. An initializer list can be used with a user
defined conversion sequence, so it's not possible to use unused space in the
union. I'm open to suggestions how to avoid the enlargement of the class.

[rsmith]

Looks like this is an implementation of DR1307. Please also add a test to test/CXX/drs/dr13xx.cpp.

clang/include/clang/Sema/Overload.h

548–549

Storing the IntListExpr here doesn't seem like it captures the necessary information. Consider:

void f2(std::pair<const char*, const char*> (&&)[]); // #1
void f2(std::string (&&)[]); // #2
void g2() { f2({"foo","bar"}); } // should call #2

Here, the InitListExpr in both cases has two elements. We don't store the converted InitListExpr, because we don't -- and aren't allowed to -- build the converted InitListExpr until we've chosen the right overload. But I think what we're supposed to do in this case is to notice that calling #1 would initialize only one element of the array (one pair), whereas calling #2 would initialize two elements of the array, so we should call #2 here.

In effect, what you need to do is to compute the effective array bound for the case where we're initializing an array of unknown bound, and prefer the conversion sequence with the lower effective array bound. InitListChecker already works this out internally, see here, but currently only does that when actually doing the conversion (when not in VerifyOnly mode); you'd need to adjust that.

Given that the code that needs this (the P0388 part) is dead code for now, perhaps the best thing would be to do only the array bound comparison in this patch, and we can compute the proper array bound for said comparison in a future patch.

clang/lib/Sema/SemaOverload.cpp

3734–3747

I think this would be simpler if structured a little differently:

• Rename CompareListInitializationSequences::Conversion to ListInitializationSequence.
• Make CompareListInitializationSequences::Compare a static member of ListInitializationSequence.
• Move the element type comparison into ...::Compare and remove the CompareListInitializationSequences class, inlining the (now very simple) constructor into its only user.

3806–3820

Should this be part of CompareListInitializationSequences too?

5111–5117

Simplify, and we may as well avoid assuming that the size fits in 64 bits since it's easy to do so here (even though there are lots of other places where we make that assumption).

[Mordante]

clang/include/clang/Sema/Overload.h

548–549

I've removed the unused code for P0338 for now. Instead of storing the InitListExpr I've stored the size difference between the array and the initializer list.

[Mordante]

• No longer store the InitListExpr instead store the size difference between the array and initializer list.
• Removed the dead code for P0388.
• Don't add overloads where the initializer list has more elements than the array to be initialized.
• Since the size validation is simpler now it's directly in CompareImplicitConversionSequences instead of the helper class CompareListInitializationSequences.

clang/include/clang/Sema/Overload.h

private:
 
     /// ConversionKind - The kind of implicit conversion sequence.
     unsigned ConversionKind : 30;
 
     /// Whether the target is really a std::initializer_list, and the
     /// sequence only represents the worst element conversion.
     unsigned StdInitializerListElement : 1;
 
+    /// Whether the target is really a constant array, and the sequence only
+    /// represents the worst element conversion.
+    unsigned ConstantArrayElement : 1;
+
+    /// The number of elements the std::initalizer_list has less then the
+    /// number of elements in the array. A value of 0 means the same number of
+    /// elements. If the std::initializer_list has more elements than the array
+    /// the conversion sequence will be marked as a bad conversion and this
+    /// field won't be used.
+    llvm::APInt ConstantArraySizeDiff{};
+
     void setKind(Kind K) {
       destruct();
       ConversionKind = K;
     }
 
     void destruct() {
       if (ConversionKind == AmbiguousConversion) Ambiguous.destruct();
     }
union {
       AmbiguousConversionSequence Ambiguous;
 
       /// When ConversionKind == BadConversion, provides the details
       /// of the bad conversion.
       BadConversionSequence Bad;
     };
 
     ImplicitConversionSequence()
-        : ConversionKind(Uninitialized), StdInitializerListElement(false) {
+        : ConversionKind(Uninitialized), StdInitializerListElement(false),
+          ConstantArrayElement(false) {
       Standard.setAsIdentityConversion();
     }
 
     ImplicitConversionSequence(const ImplicitConversionSequence &Other)
         : ConversionKind(Other.ConversionKind),
-          StdInitializerListElement(Other.StdInitializerListElement) {
+          StdInitializerListElement(Other.StdInitializerListElement),
+          ConstantArrayElement(Other.ConstantArrayElement),
+          ConstantArraySizeDiff(Other.ConstantArraySizeDiff) {
+
       switch (ConversionKind) {
       case Uninitialized: break;
       case StandardConversion: Standard = Other.Standard; break;
       case UserDefinedConversion: UserDefined = Other.UserDefined; break;
       case AmbiguousConversion: Ambiguous.copyFrom(Other.Ambiguous); break;
       case EllipsisConversion: break;
       case BadConversion: Bad = Other.Bad; break;
       }
public:
     bool isStdInitializerListElement() const {
       return StdInitializerListElement;
     }
 
     void setStdInitializerListElement(bool V = true) {
       StdInitializerListElement = V;
     }
 
+    bool isConstantArrayElement() const { return ConstantArrayElement; }
+    void setConstantArraySizeDiff(llvm::APInt Value) {
+      ConstantArrayElement = true;
+      ConstantArraySizeDiff = Value;
+    }
+    llvm::APInt getConstantArraySizeDiff() const {
+      assert(ConstantArrayElement);
+      return ConstantArraySizeDiff;
+    }
+
     /// Form an "implicit" conversion sequence from nullptr_t to bool, for a
     /// direct-initialization of a bool object from nullptr_t.
     static ImplicitConversionSequence getNullptrToBool(QualType SourceType,
                                                        QualType DestType,
                                                        bool NeedLValToRVal) {
       ImplicitConversionSequence ICS;
       ICS.setStandard();
       ICS.Standard.setAsIdentityConversion();

clang/lib/Sema/SemaOverload.cpp

 static bool hasDeprecatedStringLiteralToCharPtrConversion(
     const ImplicitConversionSequence &ICS) {
   return (ICS.isStandard() && ICS.Standard.DeprecatedStringLiteralToCharPtr) ||
          (ICS.isUserDefined() &&
           ICS.UserDefined.Before.DeprecatedStringLiteralToCharPtr);
 }
 
 /// CompareImplicitConversionSequences - Compare two implicit
 /// conversion sequences to determine whether one is better than the
 /// other or if they are indistinguishable (C++ 13.3.3.2).
 static ImplicitConversionSequence::CompareKind
 CompareImplicitConversionSequences(Sema &S, SourceLocation Loc,
                                    const ImplicitConversionSequence& ICS1,
                                    const ImplicitConversionSequence& ICS2)
 {
   // (C++ 13.3.3.2p2): When comparing the basic forms of implicit
   // conversion sequences (as defined in 13.3.3.1)
   //   -- a standard conversion sequence (13.3.3.1.1) is a better
   //      conversion sequence than a user-defined conversion sequence or
   //      an ellipsis conversion sequence, and
   //   -- a user-defined conversion sequence (13.3.3.1.2) is a better
   //      conversion sequence than an ellipsis conversion sequence
   //      (13.3.3.1.3).
   //
   // C++0x [over.best.ics]p10:
   //   For the purpose of ranking implicit conversion sequences as
   //   described in 13.3.3.2, the ambiguous conversion sequence is
   //   treated as a user-defined sequence that is indistinguishable
   //   from any other user-defined conversion sequence.
 
CompareImplicitConversionSequences(Sema &S, SourceLocation Loc,
   // List-initialization sequence L1 is a better conversion sequence than
   // list-initialization sequence L2 if:
   // - L1 converts to std::initializer_list<X> for some X and L2 does not, or,
   //   if not that,
   // - L1 converts to type "array of N1 T", L2 converts to type "array of N2 T",
   //   and N1 is smaller than N2.,
   // even if one of the other rules in this paragraph would otherwise apply.
   if (!ICS1.isBad()) {
     if (ICS1.isStdInitializerListElement() &&
         !ICS2.isStdInitializerListElement())
       return ImplicitConversionSequence::Better;
     if (!ICS1.isStdInitializerListElement() &&
         ICS2.isStdInitializerListElement())
       return ImplicitConversionSequence::Worse;
+
+    if (ICS1.isConstantArrayElement() && ICS2.isConstantArrayElement()) {
+      llvm::APInt Diff1 = ICS1.getConstantArraySizeDiff();
+      llvm::APInt Diff2 = ICS2.getConstantArraySizeDiff();
+      if (Diff1.ult(Diff2))
+        return ImplicitConversionSequence::Better;
+      if (Diff2.ult(Diff1))
+        return ImplicitConversionSequence::Worse;
+    }
   }
 
   if (ICS1.isStandard())
     // Standard conversion sequence S1 is a better conversion sequence than
     // standard conversion sequence S2 if [...]
     Result = CompareStandardConversionSequences(S, Loc,
                                                 ICS1.Standard, ICS2.Standard);
   else if (ICS1.isUserDefined()) {
TryListConversion(Sema &S, InitListExpr *From, QualType ToType,
   //   list has exactly N elements or if it has fewer than N elements and X is
   //   default-constructible, and if all the elements of the initializer list
   //   can be implicitly converted to X, the implicit conversion sequence is
   //   the worst conversion necessary to convert an element of the list to X.
   //
   // FIXME: We're missing a lot of these checks.
   bool toStdInitializerList = false;
   QualType X;
-  if (ToType->isArrayType())
+  Optional<llvm::APInt> ArraySizeDiff;
+  if (ToType->isArrayType()) {
+    // Has the initializer list exactly N elements or fewer than N elements?
+    if (const auto *CAT = S.getASTContext().getAsConstantArrayType(ToType)) {
+      if (CAT->getSize().ult(From->getNumInits()))
+        return Result;
+      ArraySizeDiff = CAT->getSize() - From->getNumInits();
+    }
     X = S.Context.getAsArrayType(ToType)->getElementType();
-  else
+  } else
     toStdInitializerList = S.isStdInitializerList(ToType, &X);
   if (!X.isNull()) {
     for (unsigned i = 0, e = From->getNumInits(); i < e; ++i) {
       Expr *Init = From->getInit(i);
       ImplicitConversionSequence ICS =
           TryCopyInitialization(S, Init, X, SuppressUserConversions,
                                 InOverloadResolution,
                                 AllowObjCWritebackConversion);
if (!X.isNull()) {
 
     // For an empty list, we won't have computed any conversion sequence.
     // Introduce the identity conversion sequence.
     if (From->getNumInits() == 0) {
       Result.setStandard();
       Result.Standard.setAsIdentityConversion();
       Result.Standard.setFromType(ToType);
       Result.Standard.setAllToTypes(ToType);
     }
 
     Result.setStdInitializerListElement(toStdInitializerList);
+    if (ArraySizeDiff)
+      Result.setConstantArraySizeDiff(*ArraySizeDiff);
     return Result;
   }
 
   // C++14 [over.ics.list]p4:
   // C++11 [over.ics.list]p3:
   //   Otherwise, if the parameter is a non-aggregate class X and overload
   //   resolution chooses a single best constructor [...] the implicit
   //   conversion sequence is a user-defined conversion sequence. If multiple
   //   constructors are viable but none is better than the others, the
   //   implicit conversion sequence is a user-defined conversion sequence.

clang/test/SemaCXX/overload-call.cpp

void Usage() {
     int B::*pmem;
     void (B::*pmf)();
 
     // These should not be ambiguous.
     f(pmem);
     f(pmf);
   }
 }
+
+#if __cplusplus >= 201103L
+// http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_defects.html#1307
+// DR1307
+// For review are we sure the example with array of unknown bounds is DR1307 and not P0388? P0388 is resolved in
+// https://reviews.llvm.org/D87566
+namespace InitializerListToArray {
+void f(int(&&)[2]); // expected-note {{candidate function not viable}}
+void f(int(&&)[3]); // expected-note {{candidate function not viable}}
+void f(int(&&)[4]); // expected-note {{candidate function not viable}}
+
+void g() {
+  f({1});
+  f({1, 2});
+  f({1, 2, 3});
+  f({1, 2, 3, 4});
+  f({1, 2, 3, 4, 5}); // expected-error {{no matching function for call to 'f'}}
+}
+
+struct S {
+  S();
+  S(double);
+};
+
+void h(S(&&)[2]); // expected-note {{candidate function not viable}}
+void h(S(&&)[3]); // expected-note {{candidate function not viable}}
+void h(S(&&)[4]); // expected-note {{candidate function not viable}}
+
+void i() {
+  h({1});
+  h({1, 2});
+  h({1, 2, 3});
+  h({1, 2, 3, 4});
+  h({1, 2, 3, 4, 5}); // expected-error {{no matching function for call to 'h'}}
+}
+
+} // namespace InitializerListToArray
+#endif