[libc++] Fix {std, ranges}::equal for vector<bool> with small storage types (#130394)

The current implementation of `{std, ranges}::equal` fails to correctly
compare `vector<bool>`s when the underlying storage type is smaller than
`int` (e.g., `unsigned char`, `unsigned short`, `uint8_t` and
`uint16_t`). See [demo](https://godbolt.org/z/j4s87s6b3)). The problem
arises due to integral promotions on the intermediate bitwise
operations, leading to incorrect final equality comparison results. This
patch fixes the issue by ensuring that `{std, ranges}::equal` operate
properly for both aligned and unaligned bits.
 
Fixes #126369.

2 files changed, 203 insertions, 8 deletions

diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp
index b37d788..02cc84c 100644
--- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/equal.pass.cpp
@@ -24,12 +24,14 @@
 // MSVC warning C4244: 'argument': conversion from 'wchar_t' to 'const _Ty', possible loss of data
 // MSVC warning C4389: '==': signed/unsigned mismatch
 // ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4242 /wd4244 /wd4389
+// XFAIL: FROZEN-CXX03-HEADERS-FIXME
 
 #include <algorithm>
 #include <cassert>
 #include <functional>
 #include <vector>
 
+#include "sized_allocator.h"
 #include "test_iterators.h"
 #include "test_macros.h"
 #include "type_algorithms.h"
@@ -173,6 +175,90 @@ TEST_CONSTEXPR_CXX20 bool test() {
     test_vector_bool<256>();
   }
 
+  // Make sure std::equal behaves properly with std::vector<bool> iterators with custom size types.
+  // See issue: https://github.com/llvm/llvm-project/issues/126369.
+  {
+    //// Tests for std::equal with aligned bits
+
+    { // Test the first (partial) word for uint8_t
+      using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
+      std::vector<bool, Alloc> in(6, true, Alloc(1));
+      std::vector<bool, Alloc> expected(8, true, Alloc(1));
+      assert(std::equal(in.begin() + 4, in.end(), expected.begin() + 4));
+    }
+    { // Test the last word for uint8_t
+      using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
+      std::vector<bool, Alloc> in(12, true, Alloc(1));
+      std::vector<bool, Alloc> expected(16, true, Alloc(1));
+      assert(std::equal(in.begin(), in.end(), expected.begin()));
+    }
+    { // Test middle words for uint8_t
+      using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
+      std::vector<bool, Alloc> in(24, true, Alloc(1));
+      std::vector<bool, Alloc> expected(29, true, Alloc(1));
+      assert(std::equal(in.begin(), in.end(), expected.begin()));
+    }
+
+    { // Test the first (partial) word for uint16_t
+      using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
+      std::vector<bool, Alloc> in(12, true, Alloc(1));
+      std::vector<bool, Alloc> expected(16, true, Alloc(1));
+      assert(std::equal(in.begin() + 4, in.end(), expected.begin() + 4));
+    }
+    { // Test the last word for uint16_t
+      using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
+      std::vector<bool, Alloc> in(24, true, Alloc(1));
+      std::vector<bool, Alloc> expected(32, true, Alloc(1));
+      assert(std::equal(in.begin(), in.end(), expected.begin()));
+    }
+    { // Test middle words for uint16_t
+      using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
+      std::vector<bool, Alloc> in(48, true, Alloc(1));
+      std::vector<bool, Alloc> expected(55, true, Alloc(1));
+      assert(std::equal(in.begin(), in.end(), expected.begin()));
+    }
+
+    //// Tests for std::equal with unaligned bits
+
+    { // Test the first (partial) word for uint8_t
+      using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
+      std::vector<bool, Alloc> in(6, true, Alloc(1));
+      std::vector<bool, Alloc> expected(8, true, Alloc(1));
+      assert(std::equal(in.begin() + 4, in.end(), expected.begin()));
+    }
+    { // Test the last word for uint8_t
+      using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
+      std::vector<bool, Alloc> in(4, true, Alloc(1));
+      std::vector<bool, Alloc> expected(8, true, Alloc(1));
+      assert(std::equal(in.begin(), in.end(), expected.begin() + 3));
+    }
+    { // Test middle words for uint8_t
+      using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
+      std::vector<bool, Alloc> in(16, true, Alloc(1));
+      std::vector<bool, Alloc> expected(24, true, Alloc(1));
+      assert(std::equal(in.begin(), in.end(), expected.begin() + 4));
+    }
+
+    { // Test the first (partial) word for uint16_t
+      using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
+      std::vector<bool, Alloc> in(12, true, Alloc(1));
+      std::vector<bool, Alloc> expected(16, true, Alloc(1));
+      assert(std::equal(in.begin() + 4, in.end(), expected.begin()));
+    }
+    { // Test the last word for uint16_t
+      using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
+      std::vector<bool, Alloc> in(12, true, Alloc(1));
+      std::vector<bool, Alloc> expected(16, true, Alloc(1));
+      assert(std::equal(in.begin(), in.end(), expected.begin() + 3));
+    }
+    { // Test the middle words for uint16_t
+      using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
+      std::vector<bool, Alloc> in(32, true, Alloc(1));
+      std::vector<bool, Alloc> expected(64, true, Alloc(1));
+      assert(std::equal(in.begin(), in.end(), expected.begin() + 4));
+    }
+  }
+
   return true;
 }
 
diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp
index 4c1c29c..3f3af71 100644
--- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp
+++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.equal/ranges.equal.pass.cpp
@@ -31,6 +31,7 @@
 #include <vector>
 
 #include "almost_satisfies_types.h"
+#include "sized_allocator.h"
 #include "test_iterators.h"
 #include "test_macros.h"
 
@@ -432,15 +433,123 @@ constexpr bool test() {
         assert(projCount == 6);
       }
     }
+  }
+
+  { // Test vector<bool>::iterator optimization
+    test_vector_bool<8>();
+    test_vector_bool<19>();
+    test_vector_bool<32>();
+    test_vector_bool<49>();
+    test_vector_bool<64>();
+    test_vector_bool<199>();
+    test_vector_bool<256>();
+  }
+
+  // Make sure std::equal behaves properly with std::vector<bool> iterators with custom size types.
+  // See issue: https://github.com/llvm/llvm-project/issues/126369.
+  {
+    //// Tests for std::equal with aligned bits
+
+    { // Test the first (partial) word for uint8_t
+      using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
+      std::vector<bool, Alloc> in(6, true, Alloc(1));
+      std::vector<bool, Alloc> expected(8, true, Alloc(1));
+      auto a = std::ranges::subrange(in.begin() + 4, in.end());
+      auto b = std::ranges::subrange(expected.begin() + 4, expected.begin() + 4 + a.size());
+      assert(std::ranges::equal(a, b));
+    }
+    { // Test the last word for uint8_t
+      using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
+      std::vector<bool, Alloc> in(12, true, Alloc(1));
+      std::vector<bool, Alloc> expected(16, true, Alloc(1));
+      auto a = std::ranges::subrange(in.begin(), in.end());
+      auto b = std::ranges::subrange(expected.begin(), expected.begin() + a.size());
+      assert(std::ranges::equal(a, b));
+    }
+    { // Test middle words for uint8_t
+      using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
+      std::vector<bool, Alloc> in(24, true, Alloc(1));
+      std::vector<bool, Alloc> expected(29, true, Alloc(1));
+      auto a = std::ranges::subrange(in.begin(), in.end());
+      auto b = std::ranges::subrange(expected.begin(), expected.begin() + a.size());
+      assert(std::ranges::equal(a, b));
+    }
 
-    { // Test vector<bool>::iterator optimization
-      test_vector_bool<8>();
-      test_vector_bool<19>();
-      test_vector_bool<32>();
-      test_vector_bool<49>();
-      test_vector_bool<64>();
-      test_vector_bool<199>();
-      test_vector_bool<256>();
+    { // Test the first (partial) word for uint16_t
+      using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
+      std::vector<bool, Alloc> in(12, true, Alloc(1));
+      std::vector<bool, Alloc> expected(16, true, Alloc(1));
+      auto a = std::ranges::subrange(in.begin() + 4, in.end());
+      auto b = std::ranges::subrange(expected.begin() + 4, expected.begin() + 4 + a.size());
+      assert(std::ranges::equal(a, b));
+    }
+    { // Test the last word for uint16_t
+      using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
+      std::vector<bool, Alloc> in(24, true, Alloc(1));
+      std::vector<bool, Alloc> expected(32, true, Alloc(1));
+      auto a = std::ranges::subrange(in.begin(), in.end());
+      auto b = std::ranges::subrange(expected.begin(), expected.begin() + a.size());
+      assert(std::ranges::equal(a, b));
+    }
+    { // Test middle words for uint16_t
+      using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
+      std::vector<bool, Alloc> in(48, true, Alloc(1));
+      std::vector<bool, Alloc> expected(55, true, Alloc(1));
+      auto a = std::ranges::subrange(in.begin(), in.end());
+      auto b = std::ranges::subrange(expected.begin(), expected.begin() + a.size());
+      assert(std::ranges::equal(a, b));
+    }
+
+    //// Tests for std::equal with unaligned bits
+
+    { // Test the first (partial) word for uint8_t
+      using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
+      std::vector<bool, Alloc> in(6, true, Alloc(1));
+      std::vector<bool, Alloc> expected(8, true, Alloc(1));
+      auto a = std::ranges::subrange(in.begin() + 4, in.end());
+      auto b = std::ranges::subrange(expected.begin(), expected.begin() + a.size());
+      assert(std::ranges::equal(a, b));
+    }
+    { // Test the last word for uint8_t
+      using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
+      std::vector<bool, Alloc> in(4, true, Alloc(1));
+      std::vector<bool, Alloc> expected(8, true, Alloc(1));
+      auto a = std::ranges::subrange(in.begin(), in.end());
+      auto b = std::ranges::subrange(expected.begin() + 3, expected.begin() + 3 + a.size());
+      assert(std::ranges::equal(a, b));
+    }
+    { // Test middle words for uint8_t
+      using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;
+      std::vector<bool, Alloc> in(16, true, Alloc(1));
+      std::vector<bool, Alloc> expected(24, true, Alloc(1));
+      auto a = std::ranges::subrange(in.begin(), in.end());
+      auto b = std::ranges::subrange(expected.begin() + 4, expected.begin() + 4 + a.size());
+      assert(std::ranges::equal(a, b));
+    }
+
+    { // Test the first (partial) word for uint16_t
+      using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
+      std::vector<bool, Alloc> in(12, true, Alloc(1));
+      std::vector<bool, Alloc> expected(16, true, Alloc(1));
+      auto a = std::ranges::subrange(in.begin() + 4, in.end());
+      auto b = std::ranges::subrange(expected.begin(), expected.begin() + a.size());
+      assert(std::ranges::equal(a, b));
+    }
+    { // Test the last word for uint16_t
+      using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
+      std::vector<bool, Alloc> in(12, true, Alloc(1));
+      std::vector<bool, Alloc> expected(16, true, Alloc(1));
+      auto a = std::ranges::subrange(in.begin(), in.end());
+      auto b = std::ranges::subrange(expected.begin() + 3, expected.begin() + 3 + a.size());
+      assert(std::ranges::equal(a, b));
+    }
+    { // Test the middle words for uint16_t
+      using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;
+      std::vector<bool, Alloc> in(32, true, Alloc(1));
+      std::vector<bool, Alloc> expected(64, true, Alloc(1));
+      auto a = std::ranges::subrange(in.begin(), in.end());
+      auto b = std::ranges::subrange(expected.begin() + 4, expected.begin() + 4 + a.size());
+      assert(std::ranges::equal(a, b));
     }
   }