<algorithm>: find()/count() (classic/ranges) regression finding -1 in unsigned int elements

[StephanTLavavej]

Reported as DevCom-10206822 and internal VSO-1684032 / AB#1684032 .

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

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

#pragma warning(disable : 4389) // signed/unsigned mismatch

void test(const bool val, const char* const str) {
    if (!val) {
        printf("FAIL! Expected: %s\n", str);
    }
}

#define VERIFY(X) test(X, #X)

int main() {
    int i = -1;
    vector<unsigned int> v;
    v.push_back(i);

    VERIFY(v[0] == i);

    VERIFY(find(v.begin(), v.end(), i) == v.begin());
    VERIFY(ranges::find(v, i) == v.begin());
    VERIFY(count(v.begin(), v.end(), i) == 1);
    VERIFY(ranges::count(v, i) == 1);
}

D:\GitHub\STL\out\x64>cl /EHsc /nologo /W4 /MTd /std:c++latest meow.cpp && meow
meow.cpp
FAIL! Expected: find(v.begin(), v.end(), i) == v.begin()
FAIL! Expected: ranges::find(v, i) == v.begin()
FAIL! Expected: count(v.begin(), v.end(), i) == 1
FAIL! Expected: ranges::count(v, i) == 1

This regressed between VS 2022 17.2 and 17.3; I believe it was caused by #2434 adding vectorized implementations of find(), count(), ranges::find(), and ranges::count(). Compiler Explorer example: https://godbolt.org/z/evhb7fhnb

Our test coverage tried to be comprehensive but clearly missed this scenario. We have tests to verify that searching for an int -1 in a range of unsigned char won't find anything, not even the unsigned char 255, because unsigned char == int promotes the unsigned char to int. (The comparison will always be false, so we can avoid inspecting the sequence entirely. Indeed, we have to, because calling memchr() would produce an incorrect result.)

STL/tests/std/tests/Dev11_0316853_find_memchr_optimization/test.cpp

Lines 277 to 296 in e28f956

	{ // Test optimized element types.
	vector<unsigned char> vuc;
	vuc.push_back(0);
	vuc.push_back(1);
	vuc.push_back(47);
	vuc.push_back(254);
	vuc.push_back(255);
	#ifdef __cpp_lib_concepts
	static_assert(_Vector_alg_in_find_is_safe<decltype(vuc.begin()), decltype(47)>, "should optimize");
	#endif // __cpp_lib_concepts
	assert(find(vuc.begin(), vuc.end(), 47) == vuc.begin() + 2);
	assert(find(vuc.begin(), vuc.end(), 255) == vuc.begin() + 4);
	assert(find(vuc.begin(), vuc.end(), -1) == vuc.end());
	assert(find(vuc.cbegin(), vuc.cend(), 47) == vuc.cbegin() + 2);
	assert(find(vuc.cbegin(), vuc.cend(), 255) == vuc.cbegin() + 4);
	assert(find(vuc.cbegin(), vuc.cend(), -1) == vuc.cend());
	}

We also tried to test the limits for all permutations of element types and value types:

STL/tests/std/tests/Dev11_0316853_find_memchr_optimization/test.cpp

Lines 43 to 121 in e28f956

	template <class ElementType, class ValueType>
	void test_limit_check_elements_impl() {
	if constexpr (is_signed_v<ElementType>) {
	using UElementType = make_unsigned_t<ElementType>;
	constexpr ElementType min_val = numeric_limits<ElementType>::min();
	constexpr ElementType max_val = numeric_limits<ElementType>::max();
	constexpr UElementType umax_val = numeric_limits<UElementType>::max();
	const ElementType sc[] = {
	min_val, min_val + 1, min_val + 2, -2, -1, -1, 0, 1, 1, 2, max_val - 2, max_val - 1, max_val};
	if constexpr (is_signed_v<ValueType>) {
	if constexpr (numeric_limits<ValueType>::min() < min_val) {
	assert(find(begin(sc), end(sc), ValueType{ValueType{min_val} - 1}) == end(sc));
	}
	if constexpr (sizeof(ElementType) <= sizeof(ValueType)) {
	assert(find(begin(sc), end(sc), ValueType{min_val}) == begin(sc));
	}
	assert(find(begin(sc), end(sc), ValueType{-1}) == begin(sc) + 4);
	assert(count(begin(sc), end(sc), ValueType{-1}) == 2);
	}
	assert(count(begin(sc), end(sc), ValueType{0}) == 1);
	assert(find(begin(sc), end(sc), ValueType{0}) == begin(sc) + 6);
	assert(find(begin(sc), end(sc), ValueType{5}) == end(sc));
	if constexpr (sizeof(ElementType) <= sizeof(ValueType)) {
	assert(find(begin(sc), end(sc), ValueType{max_val}) == begin(sc) + 12);
	assert(count(begin(sc), end(sc), ValueType{max_val}) == 1);
	if constexpr (sizeof(ElementType) < sizeof(ValueType)) {
	assert(find(begin(sc), end(sc), ValueType{ValueType{max_val} + 1}) == end(sc));
	assert(find(begin(sc), end(sc), ValueType{umax_val}) == end(sc));
	assert(count(begin(sc), end(sc), ValueType{ValueType{max_val} + 1}) == 0);
	assert(count(begin(sc), end(sc), ValueType{umax_val}) == 0);
	}
	}
	} else {
	constexpr ElementType max_val = numeric_limits<ElementType>::max();
	constexpr ValueType max_vt = numeric_limits<ValueType>::max();
	const ElementType uc[] = {0, 1, 1, 2, max_val - 2, max_val - 1, max_val};
	assert(find(begin(uc), end(uc), ValueType{0}) == begin(uc));
	assert(find(begin(uc), end(uc), ValueType{2}) == begin(uc) + 3);
	assert(find(begin(uc), end(uc), ValueType{6}) == end(uc));
	if constexpr (max_val <= max_vt) {
	assert(find(begin(uc), end(uc), ValueType{max_val - 3}) == end(uc));
	assert(find(begin(uc), end(uc), ValueType{max_val - 2}) == begin(uc) + 4);
	assert(find(begin(uc), end(uc), ValueType{max_val}) == begin(uc) + 6);
	if constexpr (max_val < max_vt) {
	assert(find(begin(uc), end(uc), ValueType{ValueType{max_val} + 1}) == end(uc));
	if constexpr (sizeof(ElementType) < sizeof(ValueType)) {
	assert(find(begin(uc), end(uc), max_vt) == end(uc));
	}
	}
	}
	}
	}
	template <class ElementType>
	void test_limit_check_elements() {
	test_limit_check_elements_impl<ElementType, signed char>();
	test_limit_check_elements_impl<ElementType, short>();
	test_limit_check_elements_impl<ElementType, int>();
	test_limit_check_elements_impl<ElementType, long>();
	test_limit_check_elements_impl<ElementType, long long>();
	test_limit_check_elements_impl<ElementType, unsigned char>();
	test_limit_check_elements_impl<ElementType, unsigned short>();
	test_limit_check_elements_impl<ElementType, unsigned int>();
	test_limit_check_elements_impl<ElementType, unsigned long>();
	test_limit_check_elements_impl<ElementType, unsigned long long>();
	}

However, in this scenario, we're trying to find an int -1 in a range containing unsigned int 0xFFFFFFFFu. Such a comparison should return true (because the int will be converted to unsigned int). As @CaseyCarter investigated this, he found that the newly generalized _Within_limits is reporting that the comparison will never return true.