Some StdLib algorithms fail /std:c++latest compilation with custom contiguous iterators (Visual Studio 2019 16.8)

[vsfeedback]

This issue has been moved from DevCom-1284527.

---

Starting with Visual Studio 2019 16.8, std::equal generates a compile error when using a custom contiguous iterator. Here is code that reproduces the error:

template <typename T>
class PointerWrapper
{
public:
    typedef std::contiguous_iterator_tag iterator_concept;
    typedef std::contiguous_iterator_tag iterator_category;
    typedef T value_type;
    typedef T& reference;
    typedef T* pointer;
    typedef ptrdiff_t difference_type;

    PointerWrapper() = default;
    PointerWrapper( pointer ptr ) :m_ptr( ptr ) { }
    bool operator!=( const PointerWrapper& iter ) const { return m_ptr != iter.m_ptr; }
    bool operator==( const PointerWrapper& iter ) const { return m_ptr == iter.m_ptr; }
    bool operator>( const PointerWrapper& iter ) const { return m_ptr > iter.m_ptr; }
    bool operator>=( const PointerWrapper& iter ) const { return m_ptr >= iter.m_ptr; }
    bool operator<( const PointerWrapper& iter ) const { return m_ptr < iter.m_ptr; }
    bool operator<=( const PointerWrapper& iter ) const { return m_ptr <= iter.m_ptr; }
    reference operator*() const { return *( m_ptr ); }
    pointer operator->() const { return &operator*(); }
    reference operator[]( ptrdiff_t off ) const { return *m_ptr; }
    PointerWrapper& operator++() { m_ptr++; return *this; }
    PointerWrapper& operator--() { m_ptr--; return *this; }
    PointerWrapper operator++( int ) { PointerWrapper it( m_ptr ); m_ptr++; return it; }
    PointerWrapper operator--( int ) { PointerWrapper it( m_ptr ); m_ptr--; return it; }
    difference_type operator-( const PointerWrapper& iter ) const { return m_ptr - iter.m_ptr; }
    PointerWrapper& operator+=( difference_type off ) { m_ptr += off; return ( *this ); }
    PointerWrapper operator+( difference_type off ) const { PointerWrapper tmp( m_ptr ); return tmp += off; }
    PointerWrapper& operator-=( difference_type off ) { return *this += -off; }
    PointerWrapper operator-( difference_type off ) const { PointerWrapper tmp( m_ptr ); return tmp -= off; }
    friend PointerWrapper operator+( ptrdiff_t off, PointerWrapper iter ) { return iter + off; }
protected:
    pointer m_ptr = nullptr;
};

int values[] { 0, 1, 2, 3, 4, 5, 6 };
PointerWrapper p0( values );
PointerWrapper p1( values+1 );
PointerWrapper p2( values+2 );
PointerWrapper p3( values+3 );

auto result = std::equal( p0, p1, p2, p3 );
auto result = std::equal( p0, p1, p2 );

This code will generate a compilation error that looks like this when compiling with /std::c++latest:

1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Professional\VC\Tools\MSVC\14.28.29333\include\xutility(5036): error : reinterpret_cast from 'PointerWrapper<int>' to 'const char *' is not allowed
1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Professional\VC\Tools\MSVC\14.28.29333\include\xutility(5121): note: in instantiation of function template specialization 'std::equal<PointerWrapper<int>, PointerWrapper<int>, std::equal_to<void>>' requested here
1>C:\Program Files (x86)\Microsoft Visual Studio\2019\Professional\VC\Tools\MSVC\14.28.29333\include\xutility(5195): note: in instantiation of function template specialization 'std::equal<PointerWrapper<int>, PointerWrapper<int>, std::equal_to<void>>' requested here
1>..\..\gear_core_tests\gear_core_tests.cpp(170): note: in instantiation of function template specialization 'std::equal<PointerWrapper<int>, PointerWrapper<int>>' requested here

The reason for this is because inside std::equal, we see the following:

STL/stl/inc/xutility

Lines 5070 to 5083 in 68b344c

	auto _UFirst1 = _Get_unwrapped(_First1);
	const auto _ULast1 = _Get_unwrapped(_Last1);
	auto _UFirst2 = _Get_unwrapped_n(_First2, _Idl_distance<_InIt1>(_UFirst1, _ULast1));
	if constexpr (_Equal_memcmp_is_safe<decltype(_UFirst1), decltype(_UFirst2), _Pr>) {
	#ifdef __cpp_lib_is_constant_evaluated
	if (!_STD is_constant_evaluated())
	#endif // __cpp_lib_is_constant_evaluated
	{
	const auto _First1_ch = reinterpret_cast<const char*>(_UFirst1);
	const auto _First2_ch = reinterpret_cast<const char*>(_UFirst2);
	const auto _Count = static_cast<size_t>(reinterpret_cast<const char*>(_ULast1) - _First1_ch);
	return _CSTD memcmp(_First1_ch, _First2_ch, _Count) == 0;
	}
	}

_UFirst1, _UFirst2, and _ULast1 are the results of _Get_unwrapped() on their respective iterator arguments. For custom contiguous iterators like the one in the example, this is effectively an identity function returning the argument itself.

Now an attempt is made to reinterpret_cast, which is of course not possible on a non-pointer-iterator, and this causes compilation failure.

It turns out that this is not a problem for std::vector::iterator and presumably other StdLib contiguous container iterators (e.g. std::string, std::array) because _Get_unwrapped has overloads that cause special behaviour for these classes due to implementation-specific details. And indeed we can hack custom iterators in the same way, but this does not change the fact that std::equal as written is not compliant with the standard. This same issue is also likely to affect other StdLib algorithms, as _Get_unwrapped is used frequently in <xutility> and other headers.

One possible fix for this (at least for std::equal) is to change the code that obtains the raw pointers for memcpy to the following. This should be valid for any object that complies with the contiguous iterator concept.

const auto _First1_ch = reinterpret_cast<const char*>(addressof(*_UFirst1));
const auto _First2_ch = reinterpret_cast<const char*>(addressof(*_UFirst2));
const auto _Count     = static_cast<size_t>(reinterpret_cast<const char*>(addressof(*_ULast1)) - _First1_ch);

[CaseyCarter]

Oops: when we added the capability to recognize general contiguous_iterators to algorithms in std we didn't teach them to properly convert general contiguous_iterators to pointers. We didn't notice because all of the contiguous_iterator test cases we added unwrap to pointers anyway.