<xutility>: ranges::find with unreachable_sentinel / __std_find_trivial_unsized_1 gives wrong result

[Ilendur]

Describe the bug

When using ranges::find on a range of integers with unreachable_sentinel as end iterator, sometimes it finds a value before the begin iterator. It only happens if _USE_STD_VECTOR_ALGORITHMS is 1, when it's using __std_find_trivial_unsized_1.

Command-line test case

>type repro.cpp
#include <cstdint>
#include <array>
#include <algorithm>
#include <print>

int main()
{
    std::array<std::uint8_t, 0x10000> arr;

    std::ranges::fill(arr, std::uint8_t{1});
    arr.back() = 0;

    std::println("begin: {}", static_cast<void*>(std::to_address(std::begin(arr))));
    std::println("end:   {}", static_cast<void*>(std::to_address(std::end(arr))));

    for (auto it = std::begin(arr); it != std::end(arr); ++it) {
        auto where = std::ranges::find(it, std::unreachable_sentinel, 0);
        auto dist = std::distance(it, where);
        if (dist < 0)
            std::println("{:p} = {}", static_cast<void*>(std::to_address(where)), dist);
    }
}

>cl /EHsc /W4 /WX /std:c++latest .\repro.cpp
Microsoft (R) C/C++ Optimizing Compiler Version 19.40.33521 for x64
Copyright (C) Microsoft Corporation.  All rights reserved.

/std:c++latest is provided as a preview of language features from the latest C++
working draft, and we're eager to hear about bugs and suggestions for improvements.
However, note that these features are provided as-is without support, and subject
to changes or removal as the working draft evolves. See
https://go.microsoft.com/fwlink/?linkid=2045807 for details.

repro.cpp
Microsoft (R) Incremental Linker Version 14.40.33521.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:repro.exe
repro.obj

>.\repro.exe
begin: 0x6802effbb0
end:   0x6802f0fbb0
0x6802effba0 = -16
0x6802effba6 = -11
0x6802effba6 = -12
0x6802effba6 = -13
0x6802effba6 = -14
0x6802effba6 = -15
0x6802effba6 = -16
0x6802effba6 = -17
0x6802effba6 = -18
0x6802effba6 = -19
0x6802effba6 = -20
0x6802effba6 = -21
0x6802effba6 = -22
0x6802effba6 = -23
0x6802effba6 = -24
0x6802effba6 = -25

Expected behavior

Expected to find the 0 at the end of the range instead of getting results before the start of the range.

STL version

Microsoft Visual Studio Community 2022
Version 17.9.2

Additional context

The bug only seems to occur at certain memory addresses, so with the test array placed on the stack, the code might not show wrong results every single run. Similar problem seems to occur with different integer sizes.

[StephanTLavavej]

Thanks for the excellent report! I can repro this reliably:

C:\Temp>type meow.cpp

#include <algorithm>
#include <cstdint>
#include <print>
using namespace std;

template <typename T>
void test() {
    T arr[1024];
    const int zero_idx = 512;

    for (int offset = 1; offset < 40; ++offset) {
        for (int start = 256; start < 256 + 64; ++start) {
            ranges::fill(arr, T{1});
            arr[start - offset] = T{0};
            arr[zero_idx]       = T{0};

            const auto where = ranges::find(arr + start, unreachable_sentinel, T{0}) - arr;

            if (where != zero_idx) {
                println("FAIL! sizeof(T)={}; offset={:2}; start={}; where={}", sizeof(T), offset, start, where);
                break;
            }
        }
    }
}

int main() {
    test<uint8_t>();
    test<uint16_t>();
    test<uint32_t>();
    test<uint64_t>();
    println("DONE");
}

C:\Temp>cl /EHsc /nologo /W4 /std:c++latest /MTd /Od /D_USE_STD_VECTOR_ALGORITHMS=0 meow.cpp && meow
meow.cpp
DONE

C:\Temp>cl /EHsc /nologo /W4 /std:c++latest /MTd /Od meow.cpp && meow
meow.cpp
FAIL! sizeof(T)=1; offset= 1; start=257; where=256
FAIL! sizeof(T)=1; offset= 2; start=258; where=256
FAIL! sizeof(T)=1; offset= 3; start=259; where=256
FAIL! sizeof(T)=1; offset= 4; start=260; where=256
FAIL! sizeof(T)=1; offset= 5; start=261; where=256
FAIL! sizeof(T)=1; offset= 6; start=262; where=256
FAIL! sizeof(T)=1; offset= 7; start=263; where=256
FAIL! sizeof(T)=1; offset= 8; start=264; where=256
FAIL! sizeof(T)=1; offset= 9; start=265; where=256
FAIL! sizeof(T)=1; offset=10; start=266; where=256
FAIL! sizeof(T)=1; offset=11; start=267; where=256
FAIL! sizeof(T)=1; offset=12; start=268; where=256
FAIL! sizeof(T)=1; offset=13; start=269; where=256
FAIL! sizeof(T)=1; offset=14; start=270; where=256
FAIL! sizeof(T)=1; offset=15; start=271; where=256
FAIL! sizeof(T)=1; offset=16; start=272; where=256
FAIL! sizeof(T)=1; offset=17; start=273; where=256
FAIL! sizeof(T)=1; offset=18; start=274; where=256
FAIL! sizeof(T)=1; offset=19; start=275; where=256
FAIL! sizeof(T)=1; offset=20; start=276; where=256
FAIL! sizeof(T)=1; offset=21; start=277; where=256
FAIL! sizeof(T)=1; offset=22; start=278; where=256
FAIL! sizeof(T)=1; offset=23; start=279; where=256
FAIL! sizeof(T)=1; offset=24; start=280; where=256
FAIL! sizeof(T)=1; offset=25; start=281; where=256
FAIL! sizeof(T)=1; offset=26; start=282; where=256
FAIL! sizeof(T)=1; offset=27; start=283; where=256
FAIL! sizeof(T)=1; offset=28; start=284; where=256
FAIL! sizeof(T)=1; offset=29; start=285; where=256
FAIL! sizeof(T)=1; offset=30; start=286; where=256
FAIL! sizeof(T)=1; offset=31; start=287; where=256
FAIL! sizeof(T)=2; offset= 1; start=257; where=256
FAIL! sizeof(T)=2; offset= 2; start=258; where=256
FAIL! sizeof(T)=2; offset= 3; start=259; where=256
FAIL! sizeof(T)=2; offset= 4; start=260; where=256
FAIL! sizeof(T)=2; offset= 5; start=261; where=256
FAIL! sizeof(T)=2; offset= 6; start=262; where=256
FAIL! sizeof(T)=2; offset= 7; start=263; where=256
FAIL! sizeof(T)=2; offset= 8; start=264; where=256
FAIL! sizeof(T)=2; offset= 9; start=265; where=256
FAIL! sizeof(T)=2; offset=10; start=266; where=256
FAIL! sizeof(T)=2; offset=11; start=267; where=256
FAIL! sizeof(T)=2; offset=12; start=268; where=256
FAIL! sizeof(T)=2; offset=13; start=269; where=256
FAIL! sizeof(T)=2; offset=14; start=270; where=256
FAIL! sizeof(T)=2; offset=15; start=271; where=256
FAIL! sizeof(T)=4; offset= 1; start=257; where=256
FAIL! sizeof(T)=4; offset= 2; start=258; where=256
FAIL! sizeof(T)=4; offset= 3; start=259; where=256
FAIL! sizeof(T)=4; offset= 4; start=260; where=256
FAIL! sizeof(T)=4; offset= 5; start=261; where=256
FAIL! sizeof(T)=4; offset= 6; start=262; where=256
FAIL! sizeof(T)=4; offset= 7; start=263; where=256
FAIL! sizeof(T)=8; offset= 1; start=257; where=256
FAIL! sizeof(T)=8; offset= 2; start=258; where=256
FAIL! sizeof(T)=8; offset= 3; start=259; where=256
DONE