| Issue |
126369
|
| Summary |
[libc++] `{std, ranges}::equal` algorithms for `vector<bool>::iterator` fail with small storage types
|
| Labels |
bug
|
| Assignees |
|
| Reporter |
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](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
![]()
_______________________________________________
llvm-bugs mailing list
llvm-bugs@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
