`<vector>`: The `vector<bool>` optimization for `copy()` performs a forbidden negative shift

[StephanTLavavej]

Found by Clang 20 UBSan in GH_000625_vector_bool_optimization. Reduced:

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

// Copyright (c) Microsoft Corporation.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <vector>
using namespace std;

const vector<bool> source = { //
    true, false, true, false, true, true, true, false, //
    true, false, true, false, true, true, true, false, //
    true, false, true, false, true, true, true, false, //
    true, false, true, false, true, true, true, false, //
    true};

void test_copy_offset_source(const size_t length) {
    const vector<bool> result = {//
        /***/ false, true, false, true, true, true, false, //
        true, false, true, false, true, true, true, false, //
        true, false, true, false, true, true, true, false, //
        true, false, true, false, true, true, true, false, //
        true};

    vector<bool> dest(length, false);
    const auto first    = source.begin() + 1;
    const auto last     = first + length;
    const auto output   = dest.begin();
    const auto res_copy = copy(first, last, output);
    assert(dest == result);
    assert(res_copy == dest.end());
}

int main() {
    test_copy_offset_source(32);
}

D:\GitHub\STL\out\x64>clang-cl /EHsc /nologo /W4 /std:c++latest -fsanitize=undefined /Zi /Fdmeow.pdb meow.cpp /link /ignore:4217 && meow
   Creating library meow.lib and object meow.exp
D:\GitHub\STL\out\x64\out\inc\vector:3863:70: runtime error: shift exponent 18446744073709551615 is too large for 32-bit type '_Vbase' (aka 'unsigned int')
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior D:\GitHub\STL\out\x64\out\inc\vector:3863:70

This line is (please ignore the line number difference due to clang-formatting):

STL/stl/inc/vector

Lines 3861 to 3862 in 0cb8132

	const auto _LastShift = _DestEnd._Myoff - _Last._Myoff;
	const auto _LastSourceVal = (*_VbLast & _LastSourceMask) << _LastShift;

Here, _LastShift is -1, which UBSan has correctly detected.

In many other places we have logic to detect whether we need to shift left or right. Instead of spot-patching this location, we should think deeply about whether any other places could be affected, or if larger changes are necessary. We should also think about whether we could get different test inputs to actually fail (because right now, the test happens to pass without UBSan).

The one bit of good news is that this appears to be the only occurrence of UB found in this optimization.

[AlexGuteniev]

There might be a simpler way to handle that.
std::rotl / std::rotr can take the negative rotation without UB, and we mask the result anyway.
Performance of rotr / rotl is the same as for a single shift on x64/x86, and apparently on Arm64 too if we pick rotr,

[AlexGuteniev]

💡 Pro-tip: add -fsanitize-trap to repro command line to have breakpoint on the failure

Edit: not an actual breakpoint, but still makes debugger break