diff --git a/libcxx/docs/Status/RangesPaper.csv b/libcxx/docs/Status/RangesPaper.csv --- a/libcxx/docs/Status/RangesPaper.csv +++ b/libcxx/docs/Status/RangesPaper.csv @@ -65,7 +65,7 @@ | [iterator.cust.swap]",Zoe Carver,✅ `[alg.req] `_: pt. 3,`indirectly_comparable `_,[projected],Nikolas Klauser,✅ `[alg.req] `_: pt. 4,"| `permutable `_ -| mergeable +| `mergeable `_ | sortable",[iterator.concepts],Konstantin Varlamov,In progress `[std.iterator.tags] `_,"| `contiguous_iterator_tag `_ | `iterator_concept specialization for pointers `_ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -242,6 +242,7 @@ __iterator/iter_swap.h __iterator/iterator.h __iterator/iterator_traits.h + __iterator/mergeable.h __iterator/move_iterator.h __iterator/next.h __iterator/ostream_iterator.h diff --git a/libcxx/include/__iterator/mergeable.h b/libcxx/include/__iterator/mergeable.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__iterator/mergeable.h @@ -0,0 +1,41 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___ITERATOR_MERGEABLE_H +#define _LIBCPP___ITERATOR_MERGEABLE_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/projected.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if !defined(_LIBCPP_HAS_NO_CONCEPTS) + +template +concept mergeable = + input_iterator<_Input1> && + input_iterator<_Input2> && + weakly_incrementable<_Output> && + indirectly_copyable<_Input1, _Output> && + indirectly_copyable<_Input2, _Output> && + indirect_strict_weak_order<_Comp, projected<_Input1, _Proj1>, projected<_Input2, _Proj2>>; + +#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ITERATOR_MERGEABLE_H diff --git a/libcxx/include/iterator b/libcxx/include/iterator --- a/libcxx/include/iterator +++ b/libcxx/include/iterator @@ -156,6 +156,11 @@ concept indirectly_comparable = indirect_binary_predicate, projected>; // since C++20 + // [alg.req.mergeable], concept mergeable +template + concept mergeable = see below; // since C++20 + template S> requires (!same_as && copyable) class common_iterator; // since C++20 @@ -619,6 +624,7 @@ #include <__iterator/iter_swap.h> #include <__iterator/iterator.h> #include <__iterator/iterator_traits.h> +#include <__iterator/mergeable.h> #include <__iterator/move_iterator.h> #include <__iterator/next.h> #include <__iterator/ostream_iterator.h> diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -628,6 +628,7 @@ module iter_swap { private header "__iterator/iter_swap.h" } module iterator { private header "__iterator/iterator.h" } module iterator_traits { private header "__iterator/iterator_traits.h" } + module mergeable { private header "__iterator/mergeable.h" } module move_iterator { private header "__iterator/move_iterator.h" } module next { private header "__iterator/next.h" } module ostream_iterator { private header "__iterator/ostream_iterator.h" } diff --git a/libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp b/libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp @@ -0,0 +1,104 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts + +// template +// concept mergeable = see below; // since C++20 + +#include + +#include + +#include "test_iterators.h" +#include "test_macros.h" + +using Comp = std::ranges::less; + +using Input = cpp20_input_iterator; +static_assert( std::input_iterator); +using InputLong = cpp20_input_iterator; +static_assert( std::input_iterator); + +using Output = cpp17_output_iterator; +static_assert( std::weakly_incrementable); + +static_assert( std::indirectly_copyable); +static_assert( std::indirectly_copyable); +static_assert( std::indirect_strict_weak_order); +static_assert( std::indirect_strict_weak_order); + +// All requirements satisfied. +static_assert( std::mergeable); + +// I1 or I2 is not an input iterator. +static_assert(!std::input_iterator); +static_assert(!std::mergeable); +static_assert(!std::mergeable); + +// O is not weakly incrementable. +struct NotWeaklyIncrementable { + int& operator*() const; +}; + +static_assert(!std::weakly_incrementable); +static_assert( std::indirectly_copyable); +static_assert( std::indirect_strict_weak_order); +static_assert(!std::mergeable); + +// I1 or I2 is not indirectly copyable into O. +struct AssignableOnlyFromInt { + AssignableOnlyFromInt& operator=(int); + template + AssignableOnlyFromInt& operator=(T) = delete; +}; +using OutputOnlyInt = cpp17_output_iterator; +static_assert( std::weakly_incrementable); + +static_assert( std::indirectly_copyable); +static_assert(!std::indirectly_copyable); +static_assert( std::indirect_strict_weak_order); +static_assert( std::mergeable); +static_assert(!std::mergeable); +static_assert(!std::mergeable); + +// No indirect strict weak order between I1 and I2 (bad comparison functor). +using GoodComp = bool(*)(int, int); +static_assert( std::indirect_strict_weak_order); +static_assert( std::mergeable); +using BadComp = bool(*)(int*, int*); +static_assert(!std::indirect_strict_weak_order); +static_assert(!std::mergeable); + +// No indirect strict weak order between I1 and I2 (bad projection). +using ToInt = int(*)(int); +using ToPtr = int*(*)(int); +static_assert( std::mergeable); +static_assert( std::mergeable); +static_assert(!std::mergeable); +static_assert(!std::mergeable); +static_assert(!std::mergeable); +static_assert(!std::mergeable); + +// The output is weakly incrementable but not an output iterator. +struct WeaklyIncrementable { + using value_type = int; + using difference_type = int; + + int& operator*() const; + WeaklyIncrementable& operator++(); + // `output_iterator` requires `i++` to return an iterator, while `weakly_incrementable` only requires `i++` to be + // defined. + void operator++(int); +}; +static_assert( std::weakly_incrementable); +static_assert( std::indirectly_copyable); +static_assert(!std::output_iterator); +static_assert( std::mergeable); diff --git a/libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.subsumption.compile.pass.cpp b/libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.subsumption.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.subsumption.compile.pass.cpp @@ -0,0 +1,37 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts + +// template +// concept mergeable = see below; // since C++20 + +#include + +#include "test_macros.h" + +template +void test_subsumption() requires std::input_iterator && std::input_iterator; + +template +void test_subsumption() requires std::weakly_incrementable; + +template +void test_subsumption() requires std::indirectly_copyable && std::indirectly_copyable; + +template +void test_subsumption() requires std::indirect_strict_weak_order; + +template +constexpr bool test_subsumption() requires std::mergeable { + return true; +} + +static_assert(test_subsumption());