[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

3690–3703

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.

3856–3861

Should this be part of CompareListInitializationSequences too?

5150–5156

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 used with an initializer list.
+    /// If so the rank algorithm needs to know about the number of elements
+    /// in the std::initializer_list or array. This information isn't stored in
+    /// the conversion sequences.
+    unsigned ExtendedTypeInfo : 1;
+
+    /// The std::initializer_list expression to convert from.
+    const InitListExpr *StandardInitializerListFrom{nullptr};
+
+    /// The std::initializer_list or array to convert to.
+    void *StandardInitializerListToType{nullptr};
+
     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),
+          ExtendedTypeInfo(false) {
       Standard.setAsIdentityConversion();
     }
 
     ImplicitConversionSequence(const ImplicitConversionSequence &Other)
         : ConversionKind(Other.ConversionKind),
-          StdInitializerListElement(Other.StdInitializerListElement) {
+          StdInitializerListElement(Other.StdInitializerListElement),
+          ExtendedTypeInfo(Other.ExtendedTypeInfo),
+          StandardInitializerListFrom(Other.StandardInitializerListFrom),
+          StandardInitializerListToType(Other.StandardInitializerListToType) {
       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:
     }
 
     /// Whether the target is really a std::initializer_list, and the
     /// sequence only represents the worst element conversion.
     bool isStdInitializerListElement() const {
       return StdInitializerListElement;
     }
 
-    void setStdInitializerListElement(bool V = true) {
+    void setStdInitializerListElement(bool V = true,
+                                      const InitListExpr *From = nullptr,
+                                      QualType ToType = QualType()) {
       StdInitializerListElement = V;
+      ExtendedTypeInfo = true;
+      StandardInitializerListFrom = From;
+      StandardInitializerListToType = ToType.getAsOpaquePtr();
+    }
+
+    bool hasExtendedTypeInfo() const { return ExtendedTypeInfo; }
+
+    const InitListExpr *getStdInitializerListFrom() const {
+      assert(ExtendedTypeInfo);
+      return StandardInitializerListFrom;
+    }
+
+    QualType getStdInitializerListToType() const {
+      assert(ExtendedTypeInfo);
+      return QualType::getFromOpaquePtr(StandardInitializerListToType);
     }
 
     /// 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;

clang/lib/Sema/SemaOverload.cpp

 
 static bool hasDeprecatedStringLiteralToCharPtrConversion(
     const ImplicitConversionSequence &ICS) {
   return (ICS.isStandard() && ICS.Standard.DeprecatedStringLiteralToCharPtr) ||
          (ICS.isUserDefined() &&
           ICS.UserDefined.Before.DeprecatedStringLiteralToCharPtr);
 }
 
+namespace {
+class CompareListInitializationSequences {
+  // List-initialization sequence L1 is a better conversion sequence than
+  // list-initialization sequence L2 if:
+  // ...
+  // - C++17:
+  //   L1 converts to type "array of N1 T", L2 converts to type "array of N2 T",
+  //   and N1 is smaller than N2.,
+  // - C++20
+  //   L1 and L2 convert to arrays of the same element type, and either the
+  //   number of elements n1 initialized by L1 is less than the number of
+  //   elements n2 initialized by L2, or n1=n2 and L2 converts to an array of
+  //   unknown bound and L1 does not,
+
+  struct Conversion {
+    enum ConversionKind {
+      Bad,
+      // Conversion to an array of known bound. The source doesn't have too
+      // many elements.
+      ConstantArray,
+      // Conversion to an array of unknown bound, requires C++20.
+      IncompleteArray
+    };
+    ConversionKind Kind{Bad};
+    // The number of elements the source has less than the target.
+    // - Zero means the source and target have the same number of elements,
+    //   or the target is an array of unknown bound.
+    uint64_t Diff{0};
+    QualType ElementType;
+
+    Conversion(Sema &S, const ImplicitConversionSequence &ICS) {
+      const InitListExpr *From = ICS.getStdInitializerListFrom();
+      QualType ToType = ICS.getStdInitializerListToType();
+
+      if (ToType->isIncompleteArrayType() && S.getLangOpts().CPlusPlus20) {
+        Kind = IncompleteArray;
+        ElementType =
+            S.Context.getAsIncompleteArrayType(ToType)->getElementType();
+
+      } else if (ToType->isConstantArrayType()) {
+        const auto *Array = S.Context.getAsConstantArrayType(ToType);
+        Diff = Array->getSize().getZExtValue();
+        if (From->getNumInits() <= Diff) {
+          Diff -= From->getNumInits();
+          Kind = ConstantArray;
+        }
+        ElementType = Array->getElementType();
+      }
+    }
+  };
+
+  static ImplicitConversionSequence::CompareKind Compare(const Conversion &C1,
+                                                         const Conversion &C2) {
+    if (C1.Kind != Conversion::Bad && C1.Kind == Conversion::Bad)
+      return ImplicitConversionSequence::Better;
+
+    if (C1.Kind == Conversion::Bad && C1.Kind != Conversion::Bad)
+      return ImplicitConversionSequence::Worse;
+
+    if (C1.Kind != Conversion::Bad && C1.Kind != Conversion::Bad) {
+      if (C1.Diff == 0 && C2.Diff == 0) {
+        if (C1.Kind == Conversion::ConstantArray &&
+            C2.Kind == Conversion::IncompleteArray)
+          return ImplicitConversionSequence::Better;
+        if (C1.Kind == Conversion::IncompleteArray &&
+            C2.Kind == Conversion::ConstantArray)
+          return ImplicitConversionSequence::Worse;
+      } else {
+        if (C1.Diff < C2.Diff)
+          return ImplicitConversionSequence::Better;
+        if (C1.Diff > C2.Diff)
+          return ImplicitConversionSequence::Worse;
+      }
+    }
+
+    return ImplicitConversionSequence::Indistinguishable;
+  }
+
+public:
+  ImplicitConversionSequence::CompareKind Result{
+      ImplicitConversionSequence::Indistinguishable};
+
+  CompareListInitializationSequences(Sema &S,
+                                     const ImplicitConversionSequence &ICS1,
+                                     const ImplicitConversionSequence &ICS2) {
+    Conversion C1(S, ICS1);
+    Conversion C2(S, ICS2);
+    if (!C1.ElementType.isNull() && !C2.ElementType.isNull() &&
+        S.Context.hasSameType(C1.ElementType, C2.ElementType))
+      Result = Compare(C1, C2);
+  }
+};
+} // namespace
+
 /// 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)
 {
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.hasExtendedTypeInfo() && ICS2.hasExtendedTypeInfo()) {
+      CompareListInitializationSequences LIS(S, ICS1, ICS2);
+      if (LIS.Result != ImplicitConversionSequence::Indistinguishable)
+        return LIS.Result;
+    }
   }
 
   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()) {
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);
+    } else if (ToType->isConstantArrayType()) {
+      // Has the initializer list exactly N elements or fewer than N elements?
+      uint64_t Size = S.getASTContext()
+                          .getAsConstantArrayType(ToType)
+                          ->getSize()
+                          .getZExtValue();
+      if (From->getNumInits() > Size)
+        Result.setBad(BadConversionSequence::no_conversion, From, ToType);
     }
 
-    Result.setStdInitializerListElement(toStdInitializerList);
+    Result.setStdInitializerListElement(toStdInitializerList, From, ToType);
     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

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
+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