<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/131718>131718</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [libc++] {std, ranges}::copy_backward fails to copy vector<bool> correctly with small storage types
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            libc++
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          winner245
      </td>
    </tr>
</table>

<pre>
    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. 
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJy0WM1u4zgSfhrmUoggU5F_Dj7ETnt2gQZ2sdNzmJNBUSWL2xQpkFSc5LDPvihS8k_sYGaxGMPodkhW1VfFYvErCu_VwSCuWblh5cuDGEJr3fqojEHHn8qHytbv6x8tghycQxNAdb3GDk0QQVkDtgE2z32oWfHMimdp-_d9JeTPo3A1m-cgTH21wAlzQP_FYmVAq0oyvmF8A8pI6xzKoN-BlgIpekUZrGPFtrJWs-IbiR1bNBBahMHU6PS7MgfwwTpxQAjvPQLjSzbP9_txcE-DbJ4zvgLlwXdCa3QQWmHIhDKBtDK-xOyQMb6lwcHEQNUgW-Gi7PWwb60LF-PKhOU-XESARmbzfVqzyuDXHqVqlBRav5MQ4ScvCbzt0aXwSmFgMMoENPQ3LYYPdBYGE4Q7YMAaKhU8aXDoBx1IXhmoRRBA8Rt6EsxY_jx-eXH6wr-wd7YeJDqWP_8NHbJvnC1ztlp5ENApozqhwZ1WxUiWm19sXVkd4LsyP1n5wviyDaGPu8p3jO8OaT6z7sD47oPx3dzUzS_V7-3vjK_oW0xo5nn6yr5P4JSReqgRWLHVqiPXim83Mx121r3fm5ny43ZG6IN1KrTdvUkpvEcX7k75UFNK3JlS1geHYtKYPwfsei1CnKQkM6JD-BG3d_rrV_WBVwMvqmnQoZGY1EgtvAevPrDeC62tFME6YIsNy58B7lr47drCx43-pBmgcQpNDXdNsGKTnOiHSiuZtghg8JRRr0IP6dzAzYcVL_AjSU_LSfUXq-PyGIQrifoUhVs5kriM0qVc72wvDiLg3pq9tCYIZdDt_VH0Ue5UeIIbHTj5CSCt8QHfegf41mslVbgJCl8qE6COumLBYMVzPFx7xpd1HFhs2OJlUvn_7c8Z0C2OOHe7aduoPOmcVPE5CIJmLL5J7MMVaJGNvz5DPxv_wfgzjDaQ8eV5O80kRgIAqqGKYIAV36ATb3sfk3s5HvK0BiC0zh7PO1GJei-cE-97g8e9RnMI7ShUTIodhsGZs8ylwz-ii7Q-u8BoLuTvOvVqVQ01XohEN3sK3CcHz3FbbP4Qw5XKqG2Ech_G2dR1wNKSK9NfxMIMHTol91N53J5UEqi4pBNvo1bGd9GkbRhfnk_xvWD1Tr2SF-PBj3kfM-XegRkrCd3C43VFcXmh71epmrJyC1_OVtfJNfo95isk7VBlF6Am9H-IjM_-SmRR-31k9O8UP4poJ5SZtmaxgYtK9kwGU826OeOR7FCeTjlwYhOXg9MYZUHCcJq6pk18m6zRsY1wZnMaa4T2eJ7ky9l0W_9pbXYIJ3VUcf-MtmsaSAU3q_AwhYk0XI8AkcMZjdsh3JtIhy8ykQio3OSsfImhTS4WG6iGAMSpHMLRujqSKqzTJWkjzznhS8cL1HgHFJv4M1m_KHjRJhFXda59Fz4OVIW3oxwrN4qIU8qMlCgTEyLRTzyNqNq3tx4l0b2JJFbYildF20C59Qj_MPodBFAuaSRSSKzz7H7k1x48BgiWplIoEmM9tkrjef0sy2blKCMc8epgB9liHcmsb-2ga3BIuQyDkS1x-jqLKE4w7RD6IdDFw-Z5PksfGP-fsXme3fJR8nM79hnonDVoB_-lw9SVjFs4sf24lcpPu0mHA0OkxELrSJSJG5_jcuHndVCSM3-fOpBP3owfmH5cePOZYFsbYCsGj2kyYv7SM_ABOw-Ns13sBxotjongQyf8T5C264ex8Up-fNl4RajR5CdqrkI7VJm0HeM7rV-n_x57Z_-NMjC-q7StGN_holzyYlGUvFnkjahzvmyK1dMC503-lD9hmTcoc_5EClQl394Y343cmPHdfn_m23x3hS5rGS--l2WCd2yp7aBos3n-n089Gl8S5xpTt1HOB7qW8OCEJsCdpUxLO0cUnS8fZ2l9OlmPtxOkKFC_qLEJj75VTRjT2qlDexo5MZFH-KfDx2062TyG9ftJMiYWGDyIoF4xkWQy8NsGKmysQzgJjp0TKzd0SWVRPLZOu-JeB4WoM-UpcklB7URDe3MhzAtjAz7y66oKjxc2yS0io3RkLv27izu1j_GAUE_7SFmHbwGNp3Tzyshbd2TfO5x4-T03THa5ZEy7I_nV95Q4whwGcaCEma7qvYhJg0FJxouNCkflcR9h76c1PvmcQdzjlwEpB25BT2316fxUKG2HPhYDNs-pCpG_PqCowTaQWurYwIzd-am5liLd0uFcdGKxCRYqHOvNWAO25FXkEspT367fE6TaR4ynMhQ3BKJnHvAVDfRXqca30Imfk9FqOJwacVVpBCGdpS4uCFMLV3uy_lzXanonSNXvFZ3QYEOLjgxTMM_PC1M1vHmI8QN1W6kQedUpLRyk80a5kC6BMY-U9wP6DB7qdVGvipV4wPVs8cT5fLUqyod2jQtZVnOc8_lSFnVTlA2KajGTT8ua182ieFBrnvMyL2bLvCj5rMyqarV4akq-zIvFatFU7Cmnu0ZnVKgy6w4P0eh6VswWs-WDFhVqH1-wOD-_HzHOWfny4NaxvFXDwbOnXCsf_FlPUEHHt68LMWIKiw0VVr6F8bmKSNxNlYVGKO0pA-Lr1OeXKTi_Xh1VaNMz09W7lH8YnF7_z_U5RZzx3ej_65r_NwAA__9HPy08">