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

[winner245]

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 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_iterators. To ensure that the standard std::equal is invoked, I wrap the input vector<bool>::iterators into standard input_iterators before calling std::equal (iterator unwrapping currently doesn't work, which is another issue to be fixed). 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: #121713, #122410, #122528

[llvmbot]

@llvm/issue-subscribers-bug

Author: Peng Liu (winner245)

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 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_iterators. To ensure that the standard std::equal is invoked, I wrap the input vector<bool>::iterators into standard input_iterators 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