[clang] p0388 array list initialization overloads

[urnathan]

Summary

This is the second part of p0388, dealing with overloads of list
initialization to incomplete array types. It extends the handling
added in D103088 to permit incomplete arrays. We have to record that
the conversion involved an incomplete array, and so (readd) a bit flag
into the standard conversion sequence object. Comparing such
conversion sequences requires knowing (a) the number of array elements
initialized and (b) whether the initialization is of an incomplete array.

This also updates the web page to indicate p0388 is implemented (there
is no feature macro).

[urnathan]

rebase

[urnathan]

ping?

[aaron.ballman]

Mostly nits from me, but one question I have is: do we want to support this as an extension in older Clang modes (with the usual diagnostics for compatibility checks)?

clang/include/clang/Sema/Overload.h

686

clang/lib/Sema/SemaOverload.cpp

3828–3829

3831–3837

5020–5022

5023

5113–5114

5118

[urnathan]

Updated diff, thanks for the comments. IYDM, can we address accepting this as an extension in <C++20 as a followup?

[aaron.ballman]

In D103908#2830608, @urnathan wrote:

Updated diff, thanks for the comments. IYDM, can we address accepting this as an extension in <C++20 as a followup?

I don't mind addressing that later. Thanks, this LGTM aside from one auto nit I had missed before.

clang/lib/Sema/SemaOverload.cpp

5079

Oops, I missed this auto earlier.

clang/test/SemaCXX/cxx20-p0388-unbound-ary.cpp

114–125

Btw, thank you for the excellent commenting in this test case -- this is the sort of thing that makes the test easier for everyone to understand.

[urnathan]

clang/test/SemaCXX/cxx20-p0388-unbound-ary.cpp

114–125

I can't really claim credit, these come from the paper :)

[urnathan]

This might need a bit of reworking, depending on how the p0388 pre-patch works out.

[rsmith]

clang/lib/Sema/SemaOverload.cpp

3827–3828

(And similarly later.)

5079

Can we give this a more descriptive name? It's not obvious to me what CTT means, and I can't work it out from the type or the initializer. Same for OIA. I think this is CompletedToType and InferredArrayBound or something like that?

[rsmith]

clang/test/SemaCXX/cxx20-p0388-unbound-ary.cpp

141

Perhaps it'd be useful to include a test that demonstrates that brace elision does not work with the rules from P0388. Example:

struct A { int x, y; };
void f(int (&&)[]); // #1
void f(A (&&)[]); // #2
void g() {
  f({1, 2, 3, 4, 5, 6});
}

Here, the "prefer to initialize fewer elements" rule would pick #2 if brace elision were supported by the overload resolution rule for list initialization sequences for arrays, but we pick #1 instead because #2 appears to be non-viable, even though a call to #2 would actually work:

struct A { int x, y; };
void f(A (&&)[]);
void g() {
    f({1, 2, 3, 4, 5, 6}); // error
    (&f)({1, 2, 3, 4, 5, 6}); // OK! No overload resolution to mess things up here.
}

[urnathan]

Added additional testcases

clang/include/clang/Sema/Overload.h

public:
     };
 
   private:
     enum {
       Uninitialized = BadConversion + 1
     };
 
     /// ConversionKind - The kind of implicit conversion sequence.
-    unsigned ConversionKind;
+    unsigned ConversionKind : 31;
+
+    // Whether the initializer list was of an incomplete array.
+    unsigned InitializerListOfIncompleteArray : 1;
 
     /// When initializing an array or std::initializer_list from an
     /// initializer-list, this is the array or std::initializer_list type being
     /// initialized. The remainder of the conversion sequence, including ToType,
     /// describe the worst conversion of an initializer to an element of the
     /// array or std::initializer_list. (Note, 'worst' is not well defined.)
     QualType InitializerListContainerType;
 
union {
       AmbiguousConversionSequence Ambiguous;
 
       /// When ConversionKind == BadConversion, provides the details
       /// of the bad conversion.
       BadConversionSequence Bad;
     };
 
     ImplicitConversionSequence()
-        : ConversionKind(Uninitialized), InitializerListContainerType() {
+        : ConversionKind(Uninitialized),
+          InitializerListOfIncompleteArray(false),
+          InitializerListContainerType() {
       Standard.setAsIdentityConversion();
     }
 
     ImplicitConversionSequence(const ImplicitConversionSequence &Other)
         : ConversionKind(Other.ConversionKind),
+          InitializerListOfIncompleteArray(
+              Other.InitializerListOfIncompleteArray),
           InitializerListContainerType(Other.InitializerListContainerType) {
       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:
     void setAsIdentityConversion(QualType T) {
       setStandard();
       Standard.setAsIdentityConversion();
       Standard.setFromType(T);
       Standard.setAllToTypes(T);
     }
 
     // True iff this is a conversion sequence from an initializer list to an
     // array or std::initializer.
     bool hasInitializerListContainerType() const {
       return !InitializerListContainerType.isNull();
     }
-    void setInitializerListContainerType(QualType T) {
+    void setInitializerListContainerType(QualType T, bool IA) {
       InitializerListContainerType = T;
+      InitializerListOfIncompleteArray = IA;
+    }
+    bool isInitializerListOfIncompleteArray() const {
+      return InitializerListOfIncompleteArray;
     }
     QualType getInitializerListContainerType() const {
       assert(hasInitializerListContainerType() &&
              "not initializer list container");
       return InitializerListContainerType;
     }
 
     /// Form an "implicit" conversion sequence from nullptr_t to bool, for a

clang/lib/AST/ASTContext.cpp

while (true) {
 
     // If we don't have two array types with the same constant bound nor two
     // incomplete array types, we've unwrapped everything we can.
     // C++20 also permits one type to be a constant array type and the other
     // to be an incomplete array type.
     // FIXME: Consider also unwrapping array of unknown bound and VLA.
     if (auto *CAT1 = dyn_cast<ConstantArrayType>(AT1)) {
       auto *CAT2 = dyn_cast<ConstantArrayType>(AT2);
-      if (!(CAT2 && CAT1->getSize() == CAT2->getSize()) &&
-          !(getLangOpts().CPlusPlus20 && AllowPiMismatch &&
-            isa<IncompleteArrayType>(AT2)))
+      if (!((CAT2 && CAT1->getSize() == CAT2->getSize()) ||
+            (AllowPiMismatch && getLangOpts().CPlusPlus20 &&
+             isa<IncompleteArrayType>(AT2))))
         return;
     } else if (isa<IncompleteArrayType>(AT1)) {
-      if (!isa<IncompleteArrayType>(AT2) &&
-          !(getLangOpts().CPlusPlus20 && AllowPiMismatch &&
-            isa<ConstantArrayType>(AT2)))
+      if (!(isa<IncompleteArrayType>(AT2) ||
+            (AllowPiMismatch && getLangOpts().CPlusPlus20 &&
+             isa<ConstantArrayType>(AT2))))
         return;
     } else {
       return;
     }
 
     T1 = AT1->getElementType();
     T2 = AT2->getElementType();
   }

clang/lib/Sema/SemaOverload.cpp

CompareImplicitConversionSequences(Sema &S, SourceLocation Loc,
   // following rules apply: (C++ 13.3.3.2p3):
 
   // 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 and L2 convert to arrays of the same element type, and either the
   //   number of elements n_1 initialized by L1 is less than the number of
-  //   elements n_2 initialized by L2, or (unimplemented:C++20) n_1 = n_2 and L2
-  //   converts to an array of unknown bound and L1 does not,
+  //   elements n_2 initialized by L2, or (C++20) n_1 = n_2 and L2 converts to
+  //   an array of unknown bound and L1 does not,
   // even if one of the other rules in this paragraph would otherwise apply.
   if (!ICS1.isBad()) {
     bool StdInit1 = false, StdInit2 = false;
     if (ICS1.hasInitializerListContainerType())
       StdInit1 = S.isStdInitializerList(ICS1.getInitializerListContainerType(),
                                         nullptr);
     if (ICS2.hasInitializerListContainerType())
       StdInit2 = S.isStdInitializerList(ICS2.getInitializerListContainerType(),
                                         nullptr);
     if (StdInit1 != StdInit2)
       return StdInit1 ? ImplicitConversionSequence::Better
                       : ImplicitConversionSequence::Worse;
 
     if (ICS1.hasInitializerListContainerType() &&
         ICS2.hasInitializerListContainerType())
       if (auto *CAT1 = S.Context.getAsConstantArrayType(
               ICS1.getInitializerListContainerType()))
         if (auto *CAT2 = S.Context.getAsConstantArrayType(
-                ICS2.getInitializerListContainerType()))
+                ICS2.getInitializerListContainerType())) {
           if (S.Context.hasSameUnqualifiedType(CAT1->getElementType(),
-                                               CAT2->getElementType()) &&
-              CAT1->getSize() != CAT2->getSize())
+                                               CAT2->getElementType())) {
+            // Both to arrays of the same element type
+            if (CAT1->getSize() != CAT2->getSize())
+              // Different sized, the smaller wins
               return CAT1->getSize().ult(CAT2->getSize())
                          ? ImplicitConversionSequence::Better
                          : ImplicitConversionSequence::Worse;
+            if (ICS1.isInitializerListOfIncompleteArray() !=
+                ICS2.isInitializerListOfIncompleteArray())
+              // One is incomplete, it loses
+              return ICS2.isInitializerListOfIncompleteArray()
+                         ? ImplicitConversionSequence::Better
+                         : 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,
                   bool AllowObjCWritebackConversion) {
   // C++11 [over.ics.list]p1:
   //   When an argument is an initializer list, it is not an expression and
   //   special rules apply for converting it to a parameter type.
 
   ImplicitConversionSequence Result;
   Result.setBad(BadConversionSequence::no_conversion, From, ToType);
 
-  // We need a complete type for what follows. Incomplete types can never be
-  // initialized from init lists.
-  if (!S.isCompleteType(From->getBeginLoc(), ToType))
+  // We need a complete type for what follows.  With one C++20 exception,
+  // incomplete types can never be initialized from init lists.
+  QualType InitTy = ToType;
+  const ArrayType *AT = S.Context.getAsArrayType(ToType);
+  if (AT && S.getLangOpts().CPlusPlus20)
+    if (const auto *IAT = dyn_cast<IncompleteArrayType>(AT))
+      // C++20 allows list initialization of an incomplete array type.
+      InitTy = IAT->getElementType();
+  if (!S.isCompleteType(From->getBeginLoc(), InitTy))
     return Result;
 
   // Per DR1467:
   //   If the parameter type is a class X and the initializer list has a single
   //   element of type cv U, where U is X or a class derived from X, the
   //   implicit conversion sequence is the one required to convert the element
   //   to the parameter type.
   //
   //   Otherwise, if the parameter type is a character array [... ]
   //   and the initializer list has a single element that is an
   //   appropriately-typed string literal (8.5.2 [dcl.init.string]), the
   //   implicit conversion sequence is the identity conversion.
   if (From->getNumInits() == 1) {
     if (ToType->isRecordType()) {
       QualType InitType = From->getInit(0)->getType();
       if (S.Context.hasSameUnqualifiedType(InitType, ToType) ||
           S.IsDerivedFrom(From->getBeginLoc(), InitType, ToType))
         return TryCopyInitialization(S, From->getInit(0), ToType,
                                      SuppressUserConversions,
                                      InOverloadResolution,
                                      AllowObjCWritebackConversion);
     }
 
-    if (const auto *AT = S.Context.getAsArrayType(ToType)) {
-      if (S.IsStringInit(From->getInit(0), AT)) {
-        InitializedEntity Entity =
+    if (AT && S.IsStringInit(From->getInit(0), AT)) {
           InitializedEntity::InitializeParameter(S.Context, ToType,
                                                  /*Consumed=*/false);
-        if (S.CanPerformCopyInitialization(Entity, From)) {
-          Result.setStandard();
-          Result.Standard.setAsIdentityConversion();
-          Result.Standard.setFromType(ToType);
-          Result.Standard.setAllToTypes(ToType);
-          return Result;
-        }
-      }
-    }
-  }
 
   // C++14 [over.ics.list]p2: Otherwise, if the parameter type [...] (below).
   // C++11 [over.ics.list]p2:
   //   If the parameter type is std::initializer_list<X> or "array of X" and
   //   all the elements can be implicitly converted to X, the implicit
   //   conversion sequence is the worst conversion necessary to convert an
   //   element of the list to X.
   //
   // C++14 [over.ics.list]p3:
   //   Otherwise, if the parameter type is "array of N X", if the initializer
   //   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.
-  QualType InitTy = ToType;
-  ArrayType const *AT = S.Context.getAsArrayType(ToType);
   if (AT || S.isStdInitializerList(ToType, &InitTy)) {
     unsigned e = From->getNumInits();
     ImplicitConversionSequence DfltElt;
     DfltElt.setBad(BadConversionSequence::no_conversion, QualType(),
                    QualType());
+    QualType ContTy = ToType;
+    bool IsUnbounded = false;
     if (AT) {
-      // Result has been initialized above as a BadConversionSequence
       InitTy = AT->getElementType();
       if (ConstantArrayType const *CT = dyn_cast<ConstantArrayType>(AT)) {
         if (CT->getSize().ult(e)) {
           // Too many inits, fatally bad
           Result.setBad(BadConversionSequence::too_many_initializers, From,
                         ToType);
-          Result.setInitializerListContainerType(ToType);
+          Result.setInitializerListContainerType(ContTy, IsUnbounded);
           return Result;
         }
         if (CT->getSize().ugt(e)) {
           // Need an init from empty {}, is there one?
           InitListExpr EmptyList(S.Context, From->getEndLoc(), None,
                                  From->getEndLoc());
           EmptyList.setType(S.Context.VoidTy);
           DfltElt = TryListConversion(
               S, &EmptyList, InitTy, SuppressUserConversions,
               InOverloadResolution, AllowObjCWritebackConversion);
           if (DfltElt.isBad()) {
             // No {} init, fatally bad
             Result.setBad(BadConversionSequence::too_few_initializers, From,
                           ToType);
-            Result.setInitializerListContainerType(ToType);
+            Result.setInitializerListContainerType(ContTy, IsUnbounded);
             return Result;
           }
         }
+      } else {
+        assert(isa<IncompleteArrayType>(AT) && "Expected incomplete array");
+        IsUnbounded = true;
+        if (!e) {
+          // Cannot convert to zero-sized.
+          Result.setBad(BadConversionSequence::too_few_initializers, From,
+                        ToType);
+          Result.setInitializerListContainerType(ContTy, IsUnbounded);
+          return Result;
+        }
+        llvm::APInt Size(S.Context.getTypeSize(S.Context.getSizeType()), e);
+        ContTy = S.Context.getConstantArrayType(InitTy, Size, nullptr,
+                                                ArrayType::Normal, 0);
       }
     }
 
     Result.setStandard();
     Result.Standard.setAsIdentityConversion();
     Result.Standard.setFromType(InitTy);
     Result.Standard.setAllToTypes(InitTy);
     for (unsigned i = 0; i < e; ++i) {
       Expr *Init = From->getInit(i);
       ImplicitConversionSequence ICS = TryCopyInitialization(
           S, Init, InitTy, SuppressUserConversions, InOverloadResolution,
           AllowObjCWritebackConversion);
 
       // Keep the worse conversion seen so far.
       // FIXME: Sequences are not totally ordered, so 'worse' can be
       // ambiguous. CWG has been informed.
       if (CompareImplicitConversionSequences(S, From->getBeginLoc(), ICS,
                                              Result) ==
           ImplicitConversionSequence::Worse) {
         Result = ICS;
         // Bail as soon as we find something unconvertible.
         if (Result.isBad()) {
-          Result.setInitializerListContainerType(ToType);
+          Result.setInitializerListContainerType(ContTy, IsUnbounded);
           return Result;
         }
       }
     }
 
     // If we needed any implicit {} initialization, compare that now.
     // over.ics.list/6 indicates we should compare that conversion.  Again CWG
     // has been informed that this might not be the best thing.
     if (!DfltElt.isBad() && CompareImplicitConversionSequences(
                                 S, From->getEndLoc(), DfltElt, Result) ==
                                 ImplicitConversionSequence::Worse)
       Result = DfltElt;
-
-    Result.setInitializerListContainerType(ToType);
+    // Record the type being initialized so that we may compare sequences
+    Result.setInitializerListContainerType(ContTy, IsUnbounded);
     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/cxx20-p0388-unbound-ary.cpp

 #else
   Inc(*(*r3)[])[] = arp; // expected-error{{cannot initialize}}
 #endif
 
   return r2;
 }
 
 } // namespace Four
+
+namespace Five {
+// from the paper
+char (&b(int(&&)[]))[1];   // #1
+char (&b(long(&&)[]))[2];  // #2
+char (&b(int(&&)[1]))[3];  // #3
+char (&b(long(&&)[1]))[4]; // #4
+char (&b(int(&&)[2]))[5];  // #5
+#if __cplusplus < 202002
+    // expected-note@-6{{cannot convert initializer}}
+    // expected-note@-6{{cannot convert initializer}}
+    // expected-note@-6{{too many initializers}}
+    // expected-note@-6{{too many initializers}}
+    // expected-note@-6{{too many initializers}}
+#endif
+
+void f() {
+  static_assert(sizeof(b({1})) == 3);
+  static_assert(sizeof(b({1, 2})) == 5);
+  static_assert(sizeof(b({1, 2, 3})) == 1);
+#if __cplusplus < 202002
+  // expected-error@-2{{no matching function}}
+#endif
+}
+} // namespace Five
+
+#if __cplusplus >= 202002
+namespace Six {
+// from over.ics.rank 3.1
+char (&f(int(&&)[]))[1];    // #1
+char (&f(double(&&)[]))[2]; // #2
+char (&f(int(&&)[2]))[3];   // #3
+
+void toto() {
+  // Calls #1: Better than #2 due to conversion, better than #3 due to bounds
+  static_assert(sizeof(f({1})) == 1);
+
+  // Calls #2: Identity conversion is better than floating-integral conversion
+  static_assert(sizeof(f({1.0})) == 2);
+
+  // Calls #2: Identity conversion is better than floating-integral conversion
+  static_assert(sizeof(f({1.0, 2.0})) == 2);
+
+  // Calls #3: Converting to array of known bound is better than to unknown
+  //           bound, and an identity conversion is better than
+  //           floating-integral conversion
+  static_assert(sizeof(f({1, 2})) == 3);
+}
+
+} // namespace Six
+
+namespace Seven {
+
+char (&f(int(&&)[]))[1];     // #1
+char (&f(double(&&)[1]))[2]; // #2
+
+void quux() {
+  // Calls #2, float-integral conversion rather than create zero-sized array
+  static_assert(sizeof(f({})) == 2);
+}
+
+} // namespace Seven
+
+namespace Eight {
+
+// brace-elision is not a thing here:
+struct A {
+  int x, y;
+};
+
+char (&f1(int(&&)[]))[1]; // #1
+char (&f1(A(&&)[]))[2];   // #2
+
+void g1() {
+  // pick #1, even though that is more elements than #2
+  // 6 ints, as opposed to 3 As
+  static_assert(sizeof(f1({1, 2, 3, 4, 5, 6})) == 1);
+}
+
+void f2(A(&&)[]); // expected-note{{candidate function not viable}}
+void g2() {
+  f2({1, 2, 3, 4, 5, 6}); // expected-error{{no matching function}}
+}
+
+void f3(A(&&)[]);
+void g3() {
+  auto &f = f3;
+
+  f({1, 2, 3, 4, 5, 6}); // OK! We're coercing to an already-selected function
+}
+
+} // namespace Eight
+
+#endif

clang/www/cxx_status.html

</tr>
     <tr>
       <td>Class template argument deduction for alias templates</td>
       <td><a href="https://wg21.link/p1814r0">P1814R0</a></td>
       <td class="none" align="center">No</td>
     </tr>
     <tr>
       <td>Permit conversions to arrays of unknown bound</td>
       <td><a href="https://wg21.link/p0388r4">P0388R4</a></td>
-      <td class="none" align="center">No</td>
+      <td class="unreleased" align="center">Clang 13</td>
     </tr>
     <tr>
       <td><tt>constinit</tt></td>
       <td><a href="https://wg21.link/p1143r2">P1143R2</a></td>
       <td class="full" align="center">Clang 10</td>
     </tr>
     <!-- Prague 2019 papers -->
     <tr>