[regression] std::array<int, 0>::begin() should be constexpr but isn't

[tonyelewis]

Bugzilla Link	40124
Resolution	FIXED
Resolved on	May 28, 2020 09:33
Version	7.0
OS	Linux
CC	@jdoerrie,@saxbophone,@ldalessa,@ldionne,@hanickadot,@mclow,@zygoloid,@zoecarver

Extended Description

Compiling the following with -fsyntax-only -std=c++17 -stdlib=libc++ :

#include <array>

template <typename Range>
inline constexpr bool f(const Range &prmRange) {
	prmRange.begin();
	return true;
}

void some_function() {
	static_assert( f( ::std::array<int, 1>{ 0 } ) );
	static_assert( f( ::std::array<int, 0>{   } ) );
}

I get:

a.cpp:11:17: error: static_assert expression is not an integral constant expression
        static_assert( f( ::std::array<int, 0>{   } ) );
                       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cpp:5:11: note: non-constexpr function 'begin' cannot be used in a constant expression
        prmRange.begin();
                 ^
a.cpp:11:17: note: in call to 'f(::std::array<int, 0>{})'
        static_assert( f( ::std::array<int, 0>{   } ) );
                       ^
/home/lewis/source/llvm/bin/../include/c++/v1/array:273:20: note: declared here
    const_iterator begin() const _NOEXCEPT {return const_iterator(data());}
                   ^
1 error generated.

It looks like the zero-size specialisation of ::std::array has some constexprs missing. From what I can see in "26.3.7.1 Class template array overview [array.overview]" and "26.3.7.8 Zero sized arrays [array.zero]" of the C++17 draft, a zero-sized array should have constexpr begin() (etc).

This appears to be a regression: on Godbolt, I'm seeing this fail to compile in this way under 7.0 and trunk, but compile cleanly under 6.0.

Thanks very much for all work on libc++.

[tonyelewis]

assigned to @ldionne

[llvmbot]

The only way I think this could be feasible implemented is by changing the iterator types of array<T, 0>, because we can't feasibly produce a non-null pointer to T without having actually constructed a T in a constant expression.

Changing the iterator types is an ABI break, and it will break plenty of existing code that depends on the iterator type being a pointer.

I'll add a comment to LWG 2157 that we should consider removing constexpr on a lot of array<T, 0>.

[tonyelewis]

Interesting. Is it crazy to suggest returning nullptr? A la Eric Niebler in the "Pythagorian Triples, Revisited" example of his recent blog post http://ericniebler.com/2018/12/05/standard-ranges/ ?

[llvmbot]

If LWG 2157 goes through as is, then it will forbid returning nullptr (https://cplusplus.github.io/LWG/issue2157)

It states:

When a and b are distinct objects of the same zero-sized array type, a.begin() and
b.begin() are not iterators over the same underlying sequence. [Note: Therefore
begin() does not return a value-initialized iterator — end note]

[tonyelewis]

Thanks for this. Again, interesting.

In the C++17 draft (n4659.pdf), "26.3.7.8 Zero sized arrays [array.zero]" point 2 says "In the case that N == 0, begin() == end() == unique value. The return value of data() is unspecified.". Does the "unique value" in that text mean that nullptr is already an invalid approach in C++17?

Would you hope/expect that your proposed change (that would make std::array<T, 0>::begin() etc non-constexpr) would be retrospectively applied as a "fix" to C++17?

If not, what's the best way to make libc++ support C++17's constexpr requirements? Or does it have to choose between violating that or something else? It looks like libstdc++ doesn't specialise for zero-size - is that violating some other part of the C++17 standard?

It seems that it'd be possible to keep the constexpr in std::array<T, 0> if the constexpr rules were relaxed to allow a reinterpret_cast between pointer types (so long as there's no dereference of the resulting pointer). Is that right? I don't suppose that's due to be added to C++20? (It doesn't look to be in the draft at https://wg21.link/std).

Thanks very much.

[llvmbot]

I think all your analysis is correct. It is currently not allowed to return nullptr, and if we had reinterpret cast in constexpr then it would be trivial to implement (I think it may be coming down the pipeline?)

[hanickadot]

Hi, I was able to fix it locally:

change std::array<T,0>::data():

_LIBCPP_INLINE_VISIBILITY
constexpr value_type* data() _NOEXCEPT {return static_cast<value_type*>(static_cast<void*>(__elems_));}
_LIBCPP_INLINE_VISIBILITY
constexpr const value_type* data() const _NOEXCEPT {return static_cast<const value_type*>(static_cast<const void*>(__elems_));}

Add constexpr to begin()/end() and other functions, I tried the change with clang/gcc/msvc/icc.

Correct me if I'm wrong about it.

[llvmbot]

Hi Hana,

That should be equivalent to reinterpret_cast, and Clang and GCC should diagnose it as an invalid constant expression. For example: https://godbolt.org/z/7RDPHv

I'm not sure how you got your result.

[llvmbot]

Hmm. Further investigation suggests GCC tolerates this in constant expressions, Clang does not. I'm pretty sure Clang is correct here, at least W.R.T. C++17.

[llvmbot]

Here's a better reproducer: https://godbolt.org/z/Xg5aSM

[zoecarver]

We might be able to use bitcast to fix this.

[llvmbot]

bitcast doesn't solve this. It returns a new object by value by copying the bits. We need to change the type of the pointer.

+Richard Smith

Do you have suggestions for generating a singular iterator/pointer value in constexpr?
Would compiler magic like __builtin_singular_iterator(T** dest, void* mem) be viable?

[llvmbot]

Here's the related GCC bug about accepting casts from void* in constant expressions: gcc.gnu.org/#65799

[zygoloid]

You should be able to specialize array<T, 0> to use a union containing a T (which is never the active union member, but can have its address taken), in the case where T has a trivial destructor:

template requires __is_trivially_destructible(T)
struct array<T, 0> {
union U {
constexpr U() : c() {}
~U() = default;

char c;
T t;

} u;

constexpr array() : u() {}
constexpr T *begin() { return &u.t; }
constexpr T *end() { return begin(); }
};

This'll result in array<T, 0> having the same size and alignment as T, which appears to match the current libc++ implementation. (This is theoretically inefficient; sizeof(array<T, 0>) need be only alignof(T), but it happens to be convenient for the purposes of this bug!)

Presumably only handling the case where T has a trivial destructor is sufficient -- at least prior to C++20 -- because it's a prerequisite for T being a literal type, which is (hopefully!) a prerequisite for array<T, N>::begin() being usable in constant expressions.

To support C++20 and beyond, you'll also need to use a union for the remaining cases (but one with a constexpr, non-defaulted destructor).

[llvmbot]

std::array is required to be an aggregate, which technically forbids this implementation. Though perhaps it doesn't matter for the zero-length case?

[zygoloid]

std::array is required to be an aggregate

Any idea why we say that? It appears to have no observable effect, other than to change the value produced by std::is_aggregate (which as I said at the time, we should never have added to the language...) =/

As a terrible hack, we could specialize is_aggregate<array<T, 0>>, but I'd prefer that we throw this back to LWG and ask them to give us implementable rules. :)

[zoecarver]

I think making __wrapper public would make array<T, 0> an aggregate type (or at least that is what my tests say). Why does that implementation make array<T, 0> a non-aggregate type?

[zygoloid]

I think making __wrapper public would make array<T, 0> an aggregate type

I don't think there's any way to make array<T, 0>{} valid but array<T, 0>{{}} ill-formed if you do that. But that's probably acceptable.

[zoecarver]

This is not great, but it actually might work: https://gist.github.com/zoecarver/cdc4d24b7adac8c0f36edee156cc2f19

It allows for it to be an aggregate type where data is a constexpr member while erroring for array<T, 0>{{}}.

[zygoloid]

Interesting idea. It requires C++14, though (non-static data member initializers make the struct a non-aggregate in C++11); when was 'constexpr' added to these member functions?

[zoecarver]

C++17, so I think we are good :)

[mclow]

*** Bug llvm/llvm-bugzilla-archive#43890 has been marked as a duplicate of this bug. ***

[ldionne]

Another attempt to fix this: https://reviews.llvm.org/D80452

It returns nullptr from an empty array's begin() and end() -- read the review for a justification of why I think it's a valid pragmatic approach given the current situation.

[ldionne]

This should be fixed by:

commit 77b9abfc8e89ca627e4f9a1cc206bea131db6db1
Author: Louis Dionne <ldionne@apple.com>
Date:   Fri May 22 09:59:48 2020 -0400

    [libc++] Complete overhaul of constexpr support in std::array

    This commit adds missing support for constexpr in std::array under all
    standard modes up to and including C++20. It also transforms the <array>
    tests to check for constexpr-friendliness under the right standard modes.

    Fixes llvm/llvm-project#39471 
    Fixes rdar://57522096
    Supersedes https://reviews.llvm.org/D60666

    Differential Revision: https://reviews.llvm.org/D80452

[mclow]

mentioned in issue llvm/llvm-bugzilla-archive#43890