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

    <tr>
        <th>Summary</th>
        <td>
            [libc++] `{std, ranges}::equal` algorithms for `vector<bool>::iterator` fail with small storage types
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            bug
      </td>
    </tr>

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

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

<pre>
    When using `std::equal` with `vector<bool>::iterator` in libc++, the function fails to compare vectors correctly for `vector<bool>` using storage types smaller than `int`, e.g., `unsigned char`, `unsigned short`, `uint8_t` and `uint16_t`. The issue arises when these small integral types are used as the underlying storage types for `vector<bool>`, where intermediate bitwise operations involving these small integral types are subject to integral promotions, leading to incorrect final equality comparison results. 

#### Bug Reproduction
I have prepared a carefully written [demo](https://godbolt.org/z/j4s87s6b3) that illustrates the incorrect equality comparisons of `std::equal` when comparing two `vector<bool>` instances. With carefully chosen storage types, input sizes, and bit offsets for the two input vectors, we've captured incorrect comparisons in every possible code path: 
- Error processing in the first, last, or middle words;
- Error processing in aligned or unaligned code paths.

For comparison purposes, the demo also provides the correct equality comparisons obtained from the standard general-form `std::equal` which works with all general `input_iterator`s. To ensure that the standard `std::equal` is invoked, I wrap the input `vector<bool>::iterator`s into standard `input_iterator`s before calling `std::equal`. Furthermore, we also provide the comparison results obtained from other implementations like MSVC-STL or libstdc++. 

#### Key observations
- While the `std::equal` optimization for `vector<bool>::iterator` fails with small integral types in libc++, the problem does not appear in other implementations such as MSVC-STL or libstdc++, nor does it occur with the standard `std::equal` implementation in libc++. 

- The same issue also carries over to the `std::ranges::equal` algorithm with the `__bit_iterator` optimization in libc++, as the range version algorithm boils down to calling the non-range version. 

This behavior is clearly a bug in libc++. It is crucial to address this issue to ensure correct functionality across all storage types for `vector<bool>`. 

Related issues: #122528, #121713
</pre>
<img width="1" height="1" alt="" src="http://email.email.llvm.org/o/eJyMVkuP27oO_jXKhpjAkfOaRRbzaIDi3rtpB7fLgWwzsVpZ9CHlBOmvP6DteWQmOaeAAcOyxMf3fSTlRPw-Im7M4t4sHieuSzXx5uhjRLbzxaSg6rT5UWOETnzcg1lmkiqT35n8Dv_qXDDLDI4-1frngGUiNvlDQRRM_mXY5hOy0_VlBj5C8EVp7H3_PECqEXZdLJOnCDvng0AiKKlpHSMMBgVKYsYyhRPsiC96WmZjgJKI3R4hnVoUkMaFgAypdlHP-ZjMMlPHON1P9W2WWRd7ECooa8fj7_fLUhOnd-s-pvWzLoCL1cvKbNkvTeGpRvAiHYJjLyhwVPRSjYJDOOBjwj27MMaoiXaCFTjp4ehihRxOn5O5nrtGdqyRsbfNDVbeJYTCp6MXBGqVAU9RwMcDhYPa_peIpCt-YpmUjde_LVNDvR11GNBVvSHdMTIEOx9dgF4ZPp1GIr1QBEbpQpIpmOxOH5u_PnDf7eEbtkxV1yvBZHdfoXYHhJZRlVCBg9Ix7roQTnBknxJGMIv7Chsyi0dj13VKraji7NbY7Z6qgkKaEu-N3f42dvtzLuuVLIvc2FvVQwIfQieJXcIB-LcsLsQvQLsr6ld-x40Kx5GuKdRHSS6WKFP4oSXzllFZk2A851sx9rHtEoj_PXyq3gqfgHY7wTQoQiNXn8PWsWJ6QaCxqwNC6drUKYRv-b1Py0fAA_IJWhLxRUAoqUJoXapNfqds3cAXZmKlv0Tpq8zHoXI9S-q14IY3MTS-qgLCkbgSk99fPe_CUF3E0MWXj1fXMh1ksiV-L6K245ZkAEMDUPrBBSE1fvDVyOQ_81gk59XZjqnptysrleMK9hiRXbjZETfXyPZlrcn9kqHtafmMx4YG03bp-V3Lkyk8EWCUjnGQ3ZnHi078UKe_sNI8v8KRXTsqVDn-k06rFhKd-fkcGhS4I1aFhHCtuU9h23GqkRtiHGR1BviI98cy_4AyqQXwTRuwwZjGZhT8L4T_ff__w833p_-qEIIvJFXjeLjYKf6DJ6BCkA-DjV5eP2ofhkAuwklt8o3_7YYZc6WJfhpVwzDqOb7YJC-OspapCNhARSgQKYFrW3Ssmy9DIF1Za-O_ioJajsSDRS39sux4COsPhHTm7TzkF3hv-oklrnkdW8pu6Zg9CtBBpyd9Apdd3KN8cOfCntinunmLzyyz5-fCn-nunJBPOI5jsPcAB2TRXW-mC1JeKjrG_qYwSldPRIo3Z6deUnyqvWq9dgdPrNVVBnQcTuCg6PYfYfma-i3clV7JJnBVxSgalRZmj1F6LenXwTdeYoZ-40omkb45_OkMfwn2GwaXtFurI-lbsM1n1i7sur-A6MdsNcsn1SavbvNbN8HNbJXfZtYu1_NJvbG7WZXvbGaz1TxflJldL5aLbLa21e1ivi7WE7-xmV1kNlvP8sXMzqerOWbZGlflKs9XzuVmnmHjfJiGcGh0hE76YDYzu8yXt5PgCgzSXxmtLbq9sVbvjrzR7TdFtxczz4KXJG8Gkk-hv2W-43rxqFCY1b2qyj7AqKnV4zVZXYfvYvW-L94zFiYdh82H-4JPdVdMS2qM3WrU4-umZdJ7kLHbkRC7HWE4bOzfAQAA___ejM2p">