-
Notifications
You must be signed in to change notification settings - Fork 1.6k
Description
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.