Skip to content

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

@StephanTLavavej

Description

@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.)

{ // 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:

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.

Metadata

Metadata

Assignees

No one assigned

    Labels

    bugSomething isn't workingfixedSomething works now, yay!high priorityImportant!

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions