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 @@ -66,7 +66,7 @@ `[alg.req] `_: pt. 3,`indirectly_comparable `_,[projected],Nikolas Klauser,✅ `[alg.req] `_: pt. 4,"| `permutable `_ | `mergeable `_ -| sortable",[iterator.concepts],Konstantin Varlamov,In progress +| `sortable `_",[iterator.concepts],Konstantin Varlamov,✅ `[std.iterator.tags] `_,"| `contiguous_iterator_tag `_ | `iterator_concept specialization for pointers `_ ",[iterator.traits],Eric Fiselier,✅ diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -255,6 +255,7 @@ __iterator/reverse_access.h __iterator/reverse_iterator.h __iterator/size.h + __iterator/sortable.h __iterator/unreachable_sentinel.h __iterator/wrap_iter.h __libcpp_version diff --git a/libcxx/include/__iterator/sortable.h b/libcxx/include/__iterator/sortable.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__iterator/sortable.h @@ -0,0 +1,37 @@ +// -*- 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_SORTABLE_H +#define _LIBCPP___ITERATOR_SORTABLE_H + +#include <__config> +#include <__functional/identity.h> +#include <__functional/ranges_operations.h> +#include <__iterator/concepts.h> +#include <__iterator/permutable.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) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +template +concept sortable = + permutable<_Iter> && + indirect_strict_weak_order<_Comp, projected<_Iter, _Proj>>; + +#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ITERATOR_SORTABLE_H diff --git a/libcxx/include/iterator b/libcxx/include/iterator --- a/libcxx/include/iterator +++ b/libcxx/include/iterator @@ -138,10 +138,10 @@ // [alg.req.ind.copy], concept indirectly_copyable template - concept indirectly_copyable = see below; // since C++20 + concept indirectly_copyable = see below; // since C++20 template - concept indirectly_copyable_storable = see below; // since C++20 + concept indirectly_copyable_storable = see below; // since C++20 // [alg.req.ind.swap], concept indirectly_swappable template @@ -152,15 +152,19 @@ concept indirectly_comparable = indirect_binary_predicate, projected>; // since C++20 -// [alg.req.permutable], concept permutable // since C++20 +// [alg.req.permutable], concept permutable template - concept permutable = see below; + concept permutable = see below; // since C++20 // [alg.req.mergeable], concept mergeable template concept mergeable = see below; // since C++20 +// [alg.req.sortable], concept sortable +template + concept sortable = see below; // since C++20 + template S> requires (!same_as && copyable) class common_iterator; // since C++20 @@ -640,6 +644,7 @@ #include <__iterator/reverse_access.h> #include <__iterator/reverse_iterator.h> #include <__iterator/size.h> +#include <__iterator/sortable.h> #include <__iterator/unreachable_sentinel.h> #include <__iterator/wrap_iter.h> #include <__memory/addressof.h> diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -640,6 +640,7 @@ module reverse_access { private header "__iterator/reverse_access.h" } module reverse_iterator { private header "__iterator/reverse_iterator.h" } module size { private header "__iterator/size.h" } + module sortable { private header "__iterator/sortable.h" } module unreachable_sentinel { private header "__iterator/unreachable_sentinel.h" } module wrap_iter { private header "__iterator/wrap_iter.h" } } diff --git a/libcxx/test/libcxx/diagnostics/detail.headers/iterator/sortable.module.verify.cpp b/libcxx/test/libcxx/diagnostics/detail.headers/iterator/sortable.module.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/detail.headers/iterator/sortable.module.verify.cpp @@ -0,0 +1,15 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// REQUIRES: modules-build + +// WARNING: This test was generated by 'generate_private_header_tests.py' +// and should not be edited manually. + +// expected-error@*:* {{use of private header from outside its module: '__iterator/sortable.h'}} +#include <__iterator/sortable.h> diff --git a/libcxx/test/std/iterators/iterator.requirements/alg.req.permutable/permutable.compile.pass.cpp b/libcxx/test/std/iterators/iterator.requirements/alg.req.permutable/permutable.compile.pass.cpp --- a/libcxx/test/std/iterators/iterator.requirements/alg.req.permutable/permutable.compile.pass.cpp +++ b/libcxx/test/std/iterators/iterator.requirements/alg.req.permutable/permutable.compile.pass.cpp @@ -14,9 +14,7 @@ #include -#include "MoveOnly.h" #include "test_iterators.h" -#include "test_macros.h" using AllConstraintsSatisfied = forward_iterator; static_assert( std::forward_iterator); diff --git a/libcxx/test/std/iterators/iterator.requirements/alg.req.sortable/sortable.compile.pass.cpp b/libcxx/test/std/iterators/iterator.requirements/alg.req.sortable/sortable.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.requirements/alg.req.sortable/sortable.compile.pass.cpp @@ -0,0 +1,51 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template +// concept sortable = see below; // since C++20 + +#include + +#include + +using CompInt = bool(*)(int, int); +using CompDefault = std::ranges::less; + +using AllConstraintsSatisfied = int*; +static_assert( std::permutable); +static_assert( std::indirect_strict_weak_order); +static_assert( std::sortable); +static_assert( std::indirect_strict_weak_order); +static_assert( std::sortable); + +struct Foo {}; +using Proj = int(*)(Foo); +static_assert( std::permutable); +static_assert(!std::indirect_strict_weak_order); +static_assert( std::indirect_strict_weak_order>); +static_assert(!std::sortable); +static_assert( std::sortable); +static_assert(!std::indirect_strict_weak_order); +static_assert( std::indirect_strict_weak_order>); +static_assert(!std::sortable); +static_assert( std::sortable); + +using NotPermutable = const int*; +static_assert(!std::permutable); +static_assert( std::indirect_strict_weak_order); +static_assert(!std::sortable); + +struct Empty {}; +using NoIndirectStrictWeakOrder = Empty*; +static_assert( std::permutable); +static_assert(!std::indirect_strict_weak_order); +static_assert(!std::sortable); diff --git a/libcxx/test/std/iterators/iterator.requirements/alg.req.sortable/sortable.subsumption.compile.pass.cpp b/libcxx/test/std/iterators/iterator.requirements/alg.req.sortable/sortable.subsumption.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.requirements/alg.req.sortable/sortable.subsumption.compile.pass.cpp @@ -0,0 +1,27 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// UNSUPPORTED: libcpp-has-no-incomplete-ranges + +// template +// concept sortable = see below; // since C++20 + +#include + +#include + +template void test_subsumption() requires std::permutable; + +template void test_subsumption() + requires std::indirect_strict_weak_order>; + +template constexpr bool test_subsumption() requires std::sortable { return true; } + +static_assert(test_subsumption());