| Issue |
131718
|
| Summary |
[libc++] {std, ranges}::copy_backward fails to copy vector<bool> correctly with small storage types
|
| Labels |
libc++
|
| Assignees |
|
| Reporter |
winner245
|
The current implementation of `std::copy_backward` and `std::ranges::copy_backward` in libc++ incorrectly copy `vector<bool>` when the underlying storage type (`__storage_type`) is smaller than `int` (e.g., `unsigned char`, `unsigned short`, `uint8_t` and `uint16_t`). Specifically, the copying operation can unintentionally zero untargeted bits, resulting in data corruption.
#### Reproducer
Here’s a minimal reproducer ([Godbolt Link](https://godbolt.org/z/6ndfGbYhY)):
```cpp
#include <limits>
#include <memory>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
template <typename T, typename Size, typename Difference>
class sized_allocator {
template <typename U, typename Sz, typename Diff>
friend class sized_allocator;
public:
using value_type = T;
using size_type = Size;
using difference_type = Difference;
using propagate_on_container_swap = std::true_type;
constexpr explicit sized_allocator(int d = 0) : data_(d) {}
template <typename U, typename Sz, typename Diff>
constexpr sized_allocator(const sized_allocator<U, Sz, Diff>& a) noexcept : data_(a.data_) {}
constexpr T* allocate(size_type n) {
if (n > max_size())
throw std::bad_array_new_length();
return std::allocator<T>().allocate(n);
}
constexpr void deallocate(T* p, size_type n) noexcept { std::allocator<T>().deallocate(p, n); }
constexpr size_type max_size() const noexcept {
return std::numeric_limits<size_type>::max() / sizeof(value_type);
}
private:
int data_;
constexpr friend bool operator==(const sized_allocator& a, const sized_allocator& b) {
return a.data_ == b.data_;
}
constexpr friend bool operator!=(const sized_allocator& a, const sized_allocator& b) {
return a.data_ != b.data_;
}
};
int main() {
using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
std::vector<bool, Alloc> in(16, false, Alloc(1));
std::vector<bool, Alloc> out(16, true, Alloc(1));
std::copy_backward(in.begin(), in.begin() + 1, out.begin() + 1); // out[0] = false; but entire word zeroed
for (std::size_t i = 0; i < out.size(); ++i)
std::cout << out[i];
}
```
##### Expected copying behavior:
- Only a single bit `out[0]` is set to `false`, while `out[1..15]` are untouched and should remain unchanged.
- Expected output: `01111111 11111111`.
##### Current erroneous copying behavior:
- The entire storage word is zeroed, setting all bits in `out[0..15]` to `false`.
- Incorrect output: `00000000 00000000`.
#### Root Cause
The erroneous copying behavior stems from the flawed bit mask computation in `std::copy_backward`:
https://github.com/llvm/llvm-project/blob/e758237352f70fad028f3947e6f0404e50fec024/libcxx/include/__algorithm/copy_backward.h#L55
where
- `~__storage_type(0)` is first integral-promoted to `int(-1)`;
- `int(-1)` is then left-shifted and right-shifted;
- Pre-C++20: Left-shifting a negative value is UB before C++20 ([[expr.shift]/3](https://eel.is/c++draft/expr.shift#note-2));
- C++20 and later: right-shifting a negative value results in sign-bit extension since C++20 ([cppreference](https://en.cppreference.com/w/cpp/language/operator_arithmetic#Bitwise_shift_operators)).
- Due to sign-bit extension, the bit mask becomes all `1`s instead of targeting specific bits, causing the entire word to be zeroed.
Clang consistently extends sign bits in right shifts even pre-C++20, making the bug reproducible across standards.
Additionally, several other bitwise operations in `copy_backward` suffer from similar promotion and shifting issues.
![]()
_______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
