312 lines · cpp
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9// <algorithm>10 11// template<InputIterator Iter1, InputIterator Iter2>12// requires HasEqualTo<Iter1::value_type, Iter2::value_type>13// constexpr bool // constexpr after c++1714// equal(Iter1 first1, Iter1 last1, Iter2 first2);15//16// Introduced in C++14:17// template<InputIterator Iter1, InputIterator Iter2>18// constexpr bool // constexpr after c++1719// equal(Iter1 first1, Iter1 last1, Iter2 first2, Iter2 last2);20 21// We test the cartesian product, so we sometimes compare differently signed types22// ADDITIONAL_COMPILE_FLAGS(gcc-style-warnings): -Wno-sign-compare23// ADDITIONAL_COMPILE_FLAGS(character-conversion-warnings): -Wno-character-conversion24 25// MSVC warning C4242: 'argument': conversion from 'int' to 'const _Ty', possible loss of data26// MSVC warning C4244: 'argument': conversion from 'wchar_t' to 'const _Ty', possible loss of data27// MSVC warning C4389: '==': signed/unsigned mismatch28// ADDITIONAL_COMPILE_FLAGS(cl-style-warnings): /wd4242 /wd4244 /wd438929// XFAIL: FROZEN-CXX03-HEADERS-FIXME30 31#include <algorithm>32#include <cassert>33#include <functional>34#include <vector>35 36#include "sized_allocator.h"37#include "test_iterators.h"38#include "test_macros.h"39#include "type_algorithms.h"40 41template <class UnderlyingType, class Iter1>42struct Test {43 template <class Iter2>44 TEST_CONSTEXPR_CXX20 void operator()() {45 UnderlyingType a[] = {0, 1, 2, 3, 4, 5};46 const unsigned s = sizeof(a) / sizeof(a[0]);47 UnderlyingType b[s] = {0, 1, 2, 5, 4, 5};48 49 assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a)));50 assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b)));51 52#if TEST_STD_VER >= 1453 assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a), std::equal_to<>()));54 assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b), std::equal_to<>()));55 56 assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s)));57 assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s - 1)));58 assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b), Iter2(b + s)));59 60 assert(std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s), std::equal_to<>()));61 assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(a), Iter2(a + s - 1), std::equal_to<>()));62 assert(!std::equal(Iter1(a), Iter1(a + s), Iter2(b), Iter2(b + s), std::equal_to<>()));63#endif64 }65};66 67struct TestNarrowingEqualTo {68 template <class UnderlyingType>69 TEST_CONSTEXPR_CXX20 void operator()() {70 TEST_DIAGNOSTIC_PUSH71 // MSVC warning C4310: cast truncates constant value72 TEST_MSVC_DIAGNOSTIC_IGNORED(4310)73 74 UnderlyingType a[] = {75 UnderlyingType(0x1000),76 UnderlyingType(0x1001),77 UnderlyingType(0x1002),78 UnderlyingType(0x1003),79 UnderlyingType(0x1004)};80 UnderlyingType b[] = {81 UnderlyingType(0x1600),82 UnderlyingType(0x1601),83 UnderlyingType(0x1602),84 UnderlyingType(0x1603),85 UnderlyingType(0x1604)};86 87 TEST_DIAGNOSTIC_POP88 89 assert(std::equal(a, a + 5, b, std::equal_to<char>()));90#if TEST_STD_VER >= 1491 assert(std::equal(a, a + 5, b, b + 5, std::equal_to<char>()));92#endif93 }94};95 96template <class UnderlyingType, class TypeList>97struct TestIter2 {98 template <class Iter1>99 TEST_CONSTEXPR_CXX20 void operator()() {100 types::for_each(TypeList(), Test<UnderlyingType, Iter1>());101 }102};103 104struct AddressCompare {105 int i = 0;106 TEST_CONSTEXPR_CXX20 AddressCompare(int) {}107 108 operator char() { return static_cast<char>(i); }109 110 friend TEST_CONSTEXPR_CXX20 bool operator==(const AddressCompare& lhs, const AddressCompare& rhs) {111 return &lhs == &rhs;112 }113 114 friend TEST_CONSTEXPR_CXX20 bool operator!=(const AddressCompare& lhs, const AddressCompare& rhs) {115 return &lhs != &rhs;116 }117};118 119#if TEST_STD_VER >= 20120class trivially_equality_comparable {121public:122 constexpr trivially_equality_comparable(int i) : i_(i) {}123 bool operator==(const trivially_equality_comparable&) const = default;124 125private:126 int i_;127};128 129#endif130 131template <std::size_t N>132TEST_CONSTEXPR_CXX20 void test_vector_bool() {133 std::vector<bool> in(N, false);134 for (std::size_t i = 0; i < N; i += 2)135 in[i] = true;136 137 { // Test equal() with aligned bytes138 std::vector<bool> out = in;139 assert(std::equal(in.begin(), in.end(), out.begin()));140#if TEST_STD_VER >= 14141 assert(std::equal(in.begin(), in.end(), out.begin(), out.end()));142#endif143 }144 145 { // Test equal() with unaligned bytes146 std::vector<bool> out(N + 8);147 std::copy(in.begin(), in.end(), out.begin() + 4);148 assert(std::equal(in.begin(), in.end(), out.begin() + 4));149#if TEST_STD_VER >= 14150 assert(std::equal(in.begin(), in.end(), out.begin() + 4, out.end() - 4));151#endif152 }153}154 155TEST_CONSTEXPR_CXX20 bool test() {156 types::for_each(types::cpp17_input_iterator_list<int*>(), TestIter2<int, types::cpp17_input_iterator_list<int*> >());157 types::for_each(158 types::cpp17_input_iterator_list<char*>(), TestIter2<char, types::cpp17_input_iterator_list<char*> >());159 types::for_each(types::cpp17_input_iterator_list<AddressCompare*>(),160 TestIter2<AddressCompare, types::cpp17_input_iterator_list<AddressCompare*> >());161 162 types::for_each(types::integral_types(), TestNarrowingEqualTo());163 164#if TEST_STD_VER >= 20165 types::for_each(166 types::cpp17_input_iterator_list<trivially_equality_comparable*>{},167 TestIter2<trivially_equality_comparable, types::cpp17_input_iterator_list<trivially_equality_comparable*>>{});168#endif169 170 { // Test vector<bool>::iterator optimization171 test_vector_bool<8>();172 test_vector_bool<19>();173 test_vector_bool<32>();174 test_vector_bool<49>();175 test_vector_bool<64>();176 test_vector_bool<199>();177 test_vector_bool<256>();178 }179 180 // Make sure std::equal behaves properly with std::vector<bool> iterators with custom size types.181 // See issue: https://llvm.org/PR126369.182 {183 //// Tests for std::equal with aligned bits184 185 { // Test the first (partial) word for uint8_t186 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;187 std::vector<bool, Alloc> in(6, true, Alloc(1));188 std::vector<bool, Alloc> expected(8, true, Alloc(1));189 assert(std::equal(in.begin() + 4, in.end(), expected.begin() + 4));190 }191 { // Test the last word for uint8_t192 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;193 std::vector<bool, Alloc> in(12, true, Alloc(1));194 std::vector<bool, Alloc> expected(16, true, Alloc(1));195 assert(std::equal(in.begin(), in.end(), expected.begin()));196 }197 { // Test middle words for uint8_t198 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;199 std::vector<bool, Alloc> in(24, true, Alloc(1));200 std::vector<bool, Alloc> expected(29, true, Alloc(1));201 assert(std::equal(in.begin(), in.end(), expected.begin()));202 }203 204 { // Test the first (partial) word for uint16_t205 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;206 std::vector<bool, Alloc> in(12, true, Alloc(1));207 std::vector<bool, Alloc> expected(16, true, Alloc(1));208 assert(std::equal(in.begin() + 4, in.end(), expected.begin() + 4));209 }210 { // Test the last word for uint16_t211 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;212 std::vector<bool, Alloc> in(24, true, Alloc(1));213 std::vector<bool, Alloc> expected(32, true, Alloc(1));214 assert(std::equal(in.begin(), in.end(), expected.begin()));215 }216 { // Test middle words for uint16_t217 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;218 std::vector<bool, Alloc> in(48, true, Alloc(1));219 std::vector<bool, Alloc> expected(55, true, Alloc(1));220 assert(std::equal(in.begin(), in.end(), expected.begin()));221 }222 223 //// Tests for std::equal with unaligned bits224 225 { // Test the first (partial) word for uint8_t226 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;227 std::vector<bool, Alloc> in(6, true, Alloc(1));228 std::vector<bool, Alloc> expected(8, true, Alloc(1));229 assert(std::equal(in.begin() + 4, in.end(), expected.begin()));230 }231 { // Test the last word for uint8_t232 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;233 std::vector<bool, Alloc> in(4, true, Alloc(1));234 std::vector<bool, Alloc> expected(8, true, Alloc(1));235 assert(std::equal(in.begin(), in.end(), expected.begin() + 3));236 }237 { // Test middle words for uint8_t238 using Alloc = sized_allocator<bool, std::uint8_t, std::int8_t>;239 std::vector<bool, Alloc> in(16, true, Alloc(1));240 std::vector<bool, Alloc> expected(24, true, Alloc(1));241 assert(std::equal(in.begin(), in.end(), expected.begin() + 4));242 }243 244 { // Test the first (partial) word for uint16_t245 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;246 std::vector<bool, Alloc> in(12, true, Alloc(1));247 std::vector<bool, Alloc> expected(16, true, Alloc(1));248 assert(std::equal(in.begin() + 4, in.end(), expected.begin()));249 }250 { // Test the last word for uint16_t251 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;252 std::vector<bool, Alloc> in(12, true, Alloc(1));253 std::vector<bool, Alloc> expected(16, true, Alloc(1));254 assert(std::equal(in.begin(), in.end(), expected.begin() + 3));255 }256 { // Test the middle words for uint16_t257 using Alloc = sized_allocator<bool, std::uint16_t, std::int16_t>;258 std::vector<bool, Alloc> in(32, true, Alloc(1));259 std::vector<bool, Alloc> expected(64, true, Alloc(1));260 assert(std::equal(in.begin(), in.end(), expected.begin() + 4));261 }262 }263 264 return true;265}266 267struct Base {};268struct Derived : virtual Base {};269 270struct TestTypes {271 template <class T>272 struct Test {273 template <class U>274 void operator()() {275 T a[] = {1, 2, 3, 4, 5, 6};276 U b[] = {1, 2, 3, 4, 5, 6};277 assert(std::equal(a, a + 6, b));278 }279 };280 281 template <class T>282 void operator()() {283 types::for_each(types::integer_types(), Test<T>());284 }285};286 287int main(int, char**) {288 test();289#if TEST_STD_VER >= 20290 static_assert(test());291#endif292 293 types::for_each(types::integer_types(), TestTypes());294 types::for_each(types::as_pointers<types::cv_qualified_versions<int> >(),295 TestIter2<int, types::as_pointers<types::cv_qualified_versions<int> > >());296 types::for_each(types::as_pointers<types::cv_qualified_versions<char> >(),297 TestIter2<char, types::as_pointers<types::cv_qualified_versions<char> > >());298 299 {300 Derived d;301 Derived* a[] = {&d, nullptr};302 Base* b[] = {&d, nullptr};303 304 assert(std::equal(a, a + 2, b));305#if TEST_STD_VER >= 14306 assert(std::equal(a, a + 2, b, b + 2));307#endif308 }309 310 return 0;311}312