`<vector>`: `_Copy_vbool()` mishandles `vector<bool>`s of size 32 and 64, revealed by `constexpr` Clang

[StephanTLavavej]

Found by an upcoming libcxx test update.

Reduced repro

D:\GitHub\STL\out\x64>type meow.cpp

#include <algorithm>
#include <cstddef>
#include <vector>
using namespace std;

template <size_t N>
constexpr bool test() {
    const vector<bool> src(N, true);
    vector<bool> dst(N, false);
    copy(src.begin(), src.end(), dst.begin());
    return src == dst;
}

int main() {
    static_assert(test<32>());
    static_assert(test<64>());
}

Size 32 error

D:\GitHub\STL\out\x64>clang-cl /EHsc /nologo /W4 /std:c++20 /MT /Od meow.cpp
meow.cpp(15,19): error: static assertion expression is not an integral constant expression
   15 |     static_assert(test<32>());
      |                   ^~~~~~~~~~
D:\GitHub\STL\out\x64\out\inc\vector(3819,59): note: shift count 32 >= width of type '_Vbase' (aka 'unsigned int')
      (32 bits)
 3819 |     const auto _LastSourceMask  = static_cast<_Vbase>(-1) >> (_VBITS - _Last._Myoff);
      |                                                           ^
D:\GitHub\STL\out\x64\out\inc\xutility(4833,16): note: in call to
      '_Copy_vbool<std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
      std::_Vb_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>>({{{}, &{*new unsigned int[1]#0}[0], 0}},
      {{{}, &{*new unsigned int[1]#0}[1], 0}}, {{{{}, &{*new unsigned int[1]#1}[0], 0}}})'
 4833 |         return _STD _Copy_vbool(_First, _Last, _Dest);
      |                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
D:\GitHub\STL\out\x64\out\inc\yvals_core.h(1928,17): note: expanded from macro '_STD'
 1928 | #define _STD    ::std::
      |                 ^
D:\GitHub\STL\out\x64\out\inc\xutility(4865,31): note: in call to
      '_Copy_unchecked<std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
      std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
      std::_Vb_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>>({{{}, &{*new unsigned int[1]#0}[0], 0}},
      {{{}, &{*new unsigned int[1]#0}[1], 0}}, {{{{}, &{*new unsigned int[1]#1}[0], 0}}})'
 4865 |     _STD _Seek_wrapped(_Dest, _STD _Copy_unchecked(_UFirst, _ULast, _STD move(_UDest)));
      |                               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
D:\GitHub\STL\out\x64\out\inc\yvals_core.h(1928,17): note: expanded from macro '_STD'
 1928 | #define _STD    ::std::
      |                 ^
meow.cpp(10,5): note: in call to 'copy<std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
      std::_Vb_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>>({{{}, &{*new unsigned int[1]#0}[0], 0}},
      {{{}, &{*new unsigned int[1]#0}[1], 0}}, {{{{}, &{*new unsigned int[1]#1}[0], 0}}})'
   10 |     copy(src.begin(), src.end(), dst.begin());
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
meow.cpp(15,19): note: in call to 'test<32ULL>()'
   15 |     static_assert(test<32>());
      |                   ^~~~~~~~~~

This correctly points to _LastSourceMask which is performing a forbidden full shift:

STL/stl/inc/vector

Lines 3817 to 3820 in 1f6e5b1

	const auto _FirstSourceMask = static_cast<_Vbase>(-1) << _First._Myoff;
	const auto _FirstDestMask = _Dest._Myoff == 0 ? 0 : (static_cast<_Vbase>(-1) >> (_VBITS - _Dest._Myoff));
	const auto _LastSourceMask = static_cast<_Vbase>(-1) >> (_VBITS - _Last._Myoff);
	const auto _LastDestMask = static_cast<_Vbase>(-1) << _DestEnd._Myoff;

It looks like we can patch this with the same pattern used for _FirstDestMask, but I haven't exhaustively verified this.

Size 64 error

meow.cpp(16,19): error: static assertion expression is not an integral constant expression
   16 |     static_assert(test<64>());
      |                   ^~~~~~~~~~
D:\GitHub\STL\out\x64\out\inc\vector(3967,25): note: read of dereferenced one-past-the-end pointer is not allowed in a
      constant expression
 3967 |             *_VbDest = (*_VbDest & _LastDestMask) | _CarryVal;
      |                         ^
D:\GitHub\STL\out\x64\out\inc\xutility(4833,16): note: in call to
      '_Copy_vbool<std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
      std::_Vb_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>>({{{}, &{*new unsigned int[2]#0}[0], 0}},
      {{{}, &{*new unsigned int[2]#0}[2], 0}}, {{{{}, &{*new unsigned int[2]#1}[0], 0}}})'
 4833 |         return _STD _Copy_vbool(_First, _Last, _Dest);
      |                ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
D:\GitHub\STL\out\x64\out\inc\yvals_core.h(1928,17): note: expanded from macro '_STD'
 1928 | #define _STD    ::std::
      |                 ^
D:\GitHub\STL\out\x64\out\inc\xutility(4865,31): note: in call to
      '_Copy_unchecked<std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
      std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
      std::_Vb_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>>({{{}, &{*new unsigned int[2]#0}[0], 0}},
      {{{}, &{*new unsigned int[2]#0}[2], 0}}, {{{{}, &{*new unsigned int[2]#1}[0], 0}}})'
 4865 |     _STD _Seek_wrapped(_Dest, _STD _Copy_unchecked(_UFirst, _ULast, _STD move(_UDest)));
      |                               ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
D:\GitHub\STL\out\x64\out\inc\yvals_core.h(1928,17): note: expanded from macro '_STD'
 1928 | #define _STD    ::std::
      |                 ^
meow.cpp(10,5): note: in call to 'copy<std::_Vb_const_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>,
      std::_Vb_iterator<std::_Wrap_alloc<std::allocator<unsigned int>>>>({{{}, &{*new unsigned int[2]#0}[0], 0}},
      {{{}, &{*new unsigned int[2]#0}[2], 0}}, {{{{}, &{*new unsigned int[2]#1}[0], 0}}})'
   10 |     copy(src.begin(), src.end(), dst.begin());
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
meow.cpp(16,19): note: in call to 'test<64ULL>()'
   16 |     static_assert(test<64>());
      |                   ^~~~~~~~~~
2 errors generated.

This one's sneaky because above there's a runtime-only optimization that absorbs this case:

STL/stl/inc/vector

Lines 3861 to 3865 in 1f6e5b1

	#if _HAS_CXX20
	if (!_STD is_constant_evaluated())
	#endif
	{
	// If _First and _Dest have matching char alignment, use memmove

Commenting it out allows runtime execution to follow the same path as constexpr evaluation, and ASan can notice the same badness that constexpr does here.

After the runtime-only optimization, things start looking bad. It starts by talking about having "Unaligned _VbFirst and _VbLast":

STL/stl/inc/vector

Lines 3897 to 3898 in 1f6e5b1

	// Unaligned _VbFirst and _VbLast require a two step copy with carry
	if (_IsRightShift) {

But in this case we're not unaligned - _Dest._Myoff is equal to _First._Myoff. So we're not _IsRightShift, but we're also not performing a left shift either. So the else block appears to perform a forbidden full shift:

STL/stl/inc/vector

Lines 3934 to 3940 in 1f6e5b1

	} else {
	const auto _SourceShift = _Dest._Myoff - _First._Myoff;
	const auto _CarryShift = _VBITS - _SourceShift;
	const auto _FirstSourceVal = (*_VbFirst & _FirstSourceMask) << _SourceShift;
	*_VbDest = (*_VbDest & _FirstDestMask) | _FirstSourceVal;
	auto _CarryVal = *_VbFirst >> _CarryShift;

When I debugged into this, I saw that _SourceShift was 0, so _CarryShift was 32. I'm not sure why constexpr evaluation didn't stop right here.

In any event, things get worse from here. Eventually we get a "read of dereferenced one-past-the-end pointer".

I think this one needs more significant surgery than just handling the forbidden full shift. It looks like we need an entire third case handling "no shift".

[AlexGuteniev]

Size 32 fix seems to be right.

Also found an ICE. Just try with 33:

#include <cassert>
#include <iostream>

#include <algorithm>
#include <cstddef>
#include <vector>

using namespace std;

template <size_t N>
constexpr bool test() {
	const vector<bool> src(N, true);
	vector<bool> dst(N, false);
	copy(src.begin(), src.end(), dst.begin());
	return src == dst;
}

int main() {
	static_assert(test<33>());
}

example.cpp
<source>(19): fatal error C1001: Internal compiler error.
(compiler file 'D:\a\_work\1\s\src\vctools\Compiler\CxxFE\sl\p1\c\constexpr\constexpr.cpp', line 9027)
 To work around this problem, try simplifying or changing the program near the locations listed above.
If possible please provide a repro here: https://developercommunity.visualstudio.com 
Please choose the Technical Support command on the Visual C++ 
 Help menu, or open the Technical Support help file for more information
Compiler returned: 2

https://godbolt.org/z/ndoG5T1cG

[AlexGuteniev]

DevCom-10875249 reported